— Dark mode

Datatähti 2022 alku

Ositus

  • Start: 2021-10-04 00:00:00
  • End: 2021-10-18 00:00:00
CSES - Datatähti 2022 alku - Results
Submission details
Task:Ositus
Sender:andreibe
Submission time:2021-10-10 17:07:22 +0300
Language:Java
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.11 s1, 2, 3details
#20.10 s1, 2, 3details
#30.11 s1, 2, 3details
#40.11 s1, 2, 3details
#50.11 s2, 3details
#60.11 s3details
#70.11 s3details

Code

import java.io.IOException;
import java.nio.file.Paths;
import java.util.*;
class Pair {
    int x;
    int y;
    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
public class Main {
    static int SIZE = 50;
    static ArrayList<HashSet<Integer>> naapurit = new ArrayList<>(SIZE*SIZE +1);
    static Random rng = new Random();
    private static final ArrayList<Integer> empty=new ArrayList<>();

    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(Paths.get("test.txt"));
        for (int i = 0; i < SIZE*SIZE+1; i++) {
            naapurit.add(new HashSet<>());
        }
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine();
            String[] parts = line.split(" ");
            int last = -1;
            for (String part : parts) {
                int ipart = Integer.parseInt(part);
                if (last != -1) {
                    naapurit.get(last).add(ipart);
                    naapurit.get(ipart).add(last);
                }
                last = ipart;
            }
        }
        for (int i = 1; i < naapurit.size(); i++) {
            HashSet<Integer> integers = naapurit.get(i);
            if (integers.isEmpty()) {
                empty.add(i);
            }
        }
        System.out.println(empty.size());
        solve();
    }
    static int tryOne(int number, int x, int y) {
        boolean b1 = insideBounds(x, y);
        if (!b1) {
            return -1;
        }
        boolean b = canBePlacedBasicRules(number, x, y);
        boolean b2 = canBePlaced(number, x, y);
        if (b && b2)  one(number, x, y);
        if (!b2 && b) {
            return -3;
        }
        if (b) {
            return 0;
        }
        return -2;
    }
    static ArrayList<Integer> order = new ArrayList<>();

    static void one(int number, int x, int y) {
        HashSet<Integer> set = naapurit.get(number);
        if (set.isEmpty()) {
            return;
        }
        added.put(number, new Pair(x,y));
        order.add(number);
        ruudukko[y][x] = number;
        try {
            Thread.sleep(1000);
            print(ruudukko);
            System.out.println();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        if (added.size() >= SIZE*SIZE-empty.size()) {
            throw new IllegalArgumentException("OH MY GOD!!!");
        }
        for (Integer integer : set) {
            int b = tryOne(integer,x+1,y);
            int b2 = tryOne(integer,x-1,y);
            int b3 = tryOne(integer,x,y+1);
            int b4 = tryOne(integer,x,y-1);
            if ((b<0 && b2 <0 && b3<0 && b4 < 0) && (b == -3 | b2 ==-3 | b3==-3 | b4==-3)) {
                int index = order.indexOf(number);
                for (int i = order.size()-1; i >= index; i = order.size()-1) {
                    int num = order.get(i);
                    Pair pair = added.get(num);
                    added.remove(num);
                    ruudukko[pair.y][pair.x] = 0;
                    order.remove(order.size()-1);
                }
                return;
            }
        }
        if (!naapuritPaikallaan(number,x,y)) {
            int index = order.indexOf(number);
            for (int i = order.size()-1; i >= index; i = order.size()-1) {
                int num = order.get(i);
                Pair pair = added.get(num);
                added.remove(num);
                ruudukko[pair.y][pair.x] = 0;
                order.remove(order.size()-1);
            }
        }
    }
    static boolean naapuritPaikallaan(int number,int x,int y) {
        Set<Integer> naap = naapurit.get(number);
        ArrayList<Integer> ruudut = new ArrayList<>();
        ruudut.add(getRuutu(x+1,y));
        ruudut.add(getRuutu(x-1,y));
        ruudut.add(getRuutu(x,y+1));
        ruudut.add(getRuutu(x,y-1));
        for (Integer integer : naap) {
            if (!ruudut.contains(integer)) {
                return false;
            }
        }
        return true;
    }
    static int getRuutu(int x, int y) {
        if (!insideBounds(x,y)) {
            return 0;
        }
        return ruudukko[x][y];
    }
    static boolean insideBounds(int x, int y) {
        return !(x > SIZE - 1 | x < 0 | y > SIZE - 1 | y < 0);
    }
    static boolean canBePlacedBasicRules(int number, int x, int y) {
        return !added.containsKey(number) && ruudukko[y][x] == 0;
    }
    static boolean canBePlaced(int number, int x, int y) {
        for (Integer integer : added.keySet()) {
            if (naapurit.get(integer).contains(number) && added.containsKey(integer)) {
                if (!isNear(added.get(integer),x,y)) {
                    return false;
                }
            }
        }
        return mahdollistaLaittaaKaikkiNaapurit(naapurit.get(number),x,y);
    }
    static int test(int x, int y,Set<Integer> set) {
        if (!insideBounds(x,y)) {
            return 0;
        }
        int r = ruudukko[y][x];
        if (r== 0) {
            return 1;
        }
        if (set.contains(r)) {
            return 1;
        }
        return 0;
    }
    static boolean mahdollistaLaittaaKaikkiNaapurit(Set<Integer> set, int x,int y) {
        int tila = 0;
        tila += test(x+1,y,set);
        tila += test(x-1,y,set);
        tila += test(x,y+1,set);
        tila += test(x,y-1,set);
        return tila >= set.size();
    }
    static void print(int[][] ar) {
        for (int[] ints : ar) {
            for (int anInt : ints) {
                System.out.printf("%4d",anInt);
            }
            System.out.print("\n");
        }
    }
    static boolean isNear(Pair pair,int x,int y) {
        boolean xsame = (pair.x == x+1 | pair.x == x-1) && y==pair.y;
        boolean ysame = (pair.y == y+1 | pair.y == y-1) && x==pair.x;
        return xsame ^ ysame;
    }
    static int[][] ruudukko = new int[SIZE][SIZE];
    static HashMap<Integer, Pair> added = new HashMap<>();

    private static void solve() {
        int l = 10000;
        while (l > 0) {
            l--;
            try {
                one(rng.nextInt(SIZE*SIZE-1)+1,rng.nextInt(SIZE),rng.nextInt(SIZE));
            } catch (IllegalArgumentException e) {
                e.printStackTrace();
                int i = 0;
                for (int[] ints : ruudukko) {
                    for (int j = 0; j < ints.length; j++) {
                        if (ints[j] == 0) {
                            ints[j] = empty.get(i);
                            i++;
                        }
                    }
                }
                print(ruudukko);
                break;
            }
        }
    }
}

Test details

Test 1

Group: 1, 2, 3

Verdict:

input
a
view save

correct output
1
view save

user output
(empty)

Error:
Exception in thread "main" java.nio.file.NoSuchFileException: test.txt
	at java.base/sun.nio.fs.UnixException.translateToIOException(UnixException.java:92)
	at java.base/sun.nio.fs.UnixException.rethrowAsIOException(UnixException.java:111)
	at java.base/sun.nio.fs.UnixException.rethrowAsIOException(UnixException.java:116)
	at java.base/sun.nio.fs.UnixFileSystemProvider.newByteChannel(UnixFileSystemProvider.java:219)
	at java.base/java.nio.file.Files.newByteChannel(Files.java:371)
	at java.base/java.nio.file.Files.newByteChannel(Files.java:422)
	at java.base/java.nio.file.spi.FileSystemProvider.newInputStream(FileSystemProvider.java:420)
	at java.base/java.nio.file.Files.newInputStream(Files.java:156)
	at java.base/java.util.Scanner.<init>(Scanner.java:718)
	at Main.main(Main.java:20)

Test 2

Group: 1, 2, 3

Verdict:

input
abcdefghij
view save

correct output
512
view save

user output
(empty)

Error:
Exception in thread "main" java.nio.file.NoSuchFileException: test.txt
	at java.base/sun.nio.fs.UnixException.translateToIOException(UnixException.java:92)
	at java.base/sun.nio.fs.UnixException.rethrowAsIOException(UnixException.java:111)
	at java.base/sun.nio.fs.UnixException.rethrowAsIOException(UnixException.java:116)
	at java.base/sun.nio.fs.UnixFileSystemProvider.newByteChannel(UnixFileSystemProvider.java:219)
	at java.base/java.nio.file.Files.newByteChannel(Files.java:371)
	at java.base/java.nio.file.Files.newByteChannel(Files.java:422)
	at java.base/java.nio.file.spi.FileSystemProvider.newInputStream(FileSystemProvider.java:420)
	at java.base/java.nio.file.Files.newInputStream(Files.java:156)
	at java.base/java.util.Scanner.<init>(Scanner.java:718)
	at Main.main(Main.java:20)

Test 3

Group: 1, 2, 3

Verdict:

input
abcabaacbc
view save

correct output
120
view save

user output
(empty)

Error:
Exception in thread "main" java.nio.file.NoSuchFileException: test.txt
	at java.base/sun.nio.fs.UnixException.translateToIOException(UnixException.java:92)
	at java.base/sun.nio.fs.UnixException.rethrowAsIOException(UnixException.java:111)
	at java.base/sun.nio.fs.UnixException.rethrowAsIOException(UnixException.java:116)
	at java.base/sun.nio.fs.UnixFileSystemProvider.newByteChannel(UnixFileSystemProvider.java:219)
	at java.base/java.nio.file.Files.newByteChannel(Files.java:371)
	at java.base/java.nio.file.Files.newByteChannel(Files.java:422)
	at java.base/java.nio.file.spi.FileSystemProvider.newInputStream(FileSystemProvider.java:420)
	at java.base/java.nio.file.Files.newInputStream(Files.java:156)
	at java.base/java.util.Scanner.<init>(Scanner.java:718)
	at Main.main(Main.java:20)

Test 4

Group: 1, 2, 3

Verdict:

input
aaxxxxxxaa
view save

correct output
4
view save

user output
(empty)

Error:
Exception in thread "main" java.nio.file.NoSuchFileException: test.txt
	at java.base/sun.nio.fs.UnixException.translateToIOException(UnixException.java:92)
	at java.base/sun.nio.fs.UnixException.rethrowAsIOException(UnixException.java:111)
	at java.base/sun.nio.fs.UnixException.rethrowAsIOException(UnixException.java:116)
	at java.base/sun.nio.fs.UnixFileSystemProvider.newByteChannel(UnixFileSystemProvider.java:219)
	at java.base/java.nio.file.Files.newByteChannel(Files.java:371)
	at java.base/java.nio.file.Files.newByteChannel(Files.java:422)
	at java.base/java.nio.file.spi.FileSystemProvider.newInputStream(FileSystemProvider.java:420)
	at java.base/java.nio.file.Files.newInputStream(Files.java:156)
	at java.base/java.util.Scanner.<init>(Scanner.java:718)
	at Main.main(Main.java:20)

Test 5

Group: 2, 3

Verdict:

input
mfyzvoxmppoxcvktmcjkryyocfweub...
view save

correct output
643221148
view save

user output
(empty)

Error:
Exception in thread "main" java.nio.file.NoSuchFileException: test.txt
	at java.base/sun.nio.fs.UnixException.translateToIOException(UnixException.java:92)
	at java.base/sun.nio.fs.UnixException.rethrowAsIOException(UnixException.java:111)
	at java.base/sun.nio.fs.UnixException.rethrowAsIOException(UnixException.java:116)
	at java.base/sun.nio.fs.UnixFileSystemProvider.newByteChannel(UnixFileSystemProvider.java:219)
	at java.base/java.nio.file.Files.newByteChannel(Files.java:371)
	at java.base/java.nio.file.Files.newByteChannel(Files.java:422)
	at java.base/java.nio.file.spi.FileSystemProvider.newInputStream(FileSystemProvider.java:420)
	at java.base/java.nio.file.Files.newInputStream(Files.java:156)
	at java.base/java.util.Scanner.<init>(Scanner.java:718)
	at Main.main(Main.java:20)

Test 6

Group: 3

Verdict:

input
weinscqmmpgbrlboocvtbptgbahmwv...
view save

correct output
831644159
view save

user output
(empty)

Error:
Exception in thread "main" java.nio.file.NoSuchFileException: test.txt
	at java.base/sun.nio.fs.UnixException.translateToIOException(UnixException.java:92)
	at java.base/sun.nio.fs.UnixException.rethrowAsIOException(UnixException.java:111)
	at java.base/sun.nio.fs.UnixException.rethrowAsIOException(UnixException.java:116)
	at java.base/sun.nio.fs.UnixFileSystemProvider.newByteChannel(UnixFileSystemProvider.java:219)
	at java.base/java.nio.file.Files.newByteChannel(Files.java:371)
	at java.base/java.nio.file.Files.newByteChannel(Files.java:422)
	at java.base/java.nio.file.spi.FileSystemProvider.newInputStream(FileSystemProvider.java:420)
	at java.base/java.nio.file.Files.newInputStream(Files.java:156)
	at java.base/java.util.Scanner.<init>(Scanner.java:718)
	at Main.main(Main.java:20)

Test 7

Group: 3

Verdict:

input
sxaoxcyrjoeieyinaqxwukgzdnhhsw...
view save

correct output
816016015
view save

user output
(empty)

Error:
Exception in thread "main" java.nio.file.NoSuchFileException: test.txt
	at java.base/sun.nio.fs.UnixException.translateToIOException(UnixException.java:92)
	at java.base/sun.nio.fs.UnixException.rethrowAsIOException(UnixException.java:111)
	at java.base/sun.nio.fs.UnixException.rethrowAsIOException(UnixException.java:116)
	at java.base/sun.nio.fs.UnixFileSystemProvider.newByteChannel(UnixFileSystemProvider.java:219)
	at java.base/java.nio.file.Files.newByteChannel(Files.java:371)
	at java.base/java.nio.file.Files.newByteChannel(Files.java:422)
	at java.base/java.nio.file.spi.FileSystemProvider.newInputStream(FileSystemProvider.java:420)
	at java.base/java.nio.file.Files.newInputStream(Files.java:156)
	at java.base/java.util.Scanner.<init>(Scanner.java:718)
	at Main.main(Main.java:20)

Tasks

A Karkit-B Merkkijono-C Spiraali-D Ositus-E Tietoverkko-F Alue 50-

Submissions (andreibe)

2021-10-11 21:41:03 1002021-10-11 08:42:12 02021-10-11 08:10:15 02021-10-10 18:36:36 02021-10-10 17:07:56 02021-10-10 17:07:22 02021-10-05 13:40:41 402021-10-05 13:40:21 02021-10-05 12:51:15 0