oj.uz

Submission #361652

# Submission time Handle Problem Language Result Execution time Memory
361652 2021-01-31T02:49:38 Z AnythingWithJ Carnival (CEOI14_carnival) Java 11
20 / 100
 937 ms 14560 KB 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.TreeSet;

public class carnival {
    // 1 hour planning
    static int [] father,height;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        father = new int [N+1];
        height = new int [N+1];
        for (int i = 1; i <= N; i++) {
            father[i] = i;
        }
        for (int i = 1; i <= N; i+=3) {
            ArrayList<Integer> toPrint = new ArrayList<>();
            for (int j = i; j <= Math.min(i+2,N); j++) {
                toPrint.add(j);
            }
            if (toPrint.size() == 1) continue;
            System.out.print(toPrint.size()+" ");
            for (int j = 0; j < toPrint.size(); j++) {
                System.out.print(toPrint.get(j)+" ");
            }
            System.out.println();
            System.out.flush();
            int feedBack = Integer.parseInt(br.readLine());
            if (feedBack == 1) {
                for (int j = 1; j < toPrint.size(); j++) {
                    unite(toPrint.get(j),toPrint.get(j-1));
                }
            }
            else if (feedBack == 2) {
                if (toPrint.size() == 2) continue;
                else {
                    System.out.println(2+" "+toPrint.get(0)+" "+toPrint.get(1));
                    System.out.flush();
                    feedBack = Integer.parseInt(br.readLine());
                    if (feedBack == 1) {
                        unite(toPrint.get(0),toPrint.get(1));
                    }
                    else {
                        System.out.println(2+" "+toPrint.get(0)+" "+toPrint.get(2));
                        System.out.flush();
                        feedBack = Integer.parseInt(br.readLine());
                        if (feedBack == 1) {
                            unite(toPrint.get(0),toPrint.get(2));
                        }
                        else {
                            unite(toPrint.get(1),toPrint.get(2));
                        }
                    }
                }
            }
        }
        int margin = 6;
        while (margin/2 < N) {
            for (int i = 1; i <= N; i+=margin) {
                if (i+margin-1 <= N) System.out.print(margin+" ");
                else {
                    if (N-i+1 <= margin/2) continue;
                    System.out.print((N-i+1)+" ");
                }
                HashSet<Integer> set = new HashSet<>();
                for (int j =i; j <= Math.min(i+margin-1,N); j++) {
                    System.out.print(j+" ");
                    set.add(find(j));
                }
                System.out.println();
                System.out.flush();
                int feedBack = Integer.parseInt(br.readLine());
                if (feedBack == set.size()) continue;
                //int numMatches = set.size() - feedBack;
                boolean [] hasMatched = new boolean[margin/2];
                HashSet<Integer> costumeVis = new HashSet<>();
                //System.out.print(Math.min(margin/2,N-i+1-margin/2)+" ");
                secondSetLoop: for (int j = i+margin/2; j <= Math.min(i+margin-1,N); j++) {
                    if (costumeVis.contains(find(j))) continue;
                    costumeVis.add(find(j));
                    HashSet<Integer> firstSetCostumeVis = new HashSet<>();
                    firstSetLoop: for (int x = i; x <= i+margin/2-1;x++) {
                        if (hasMatched[x-i]) continue;
                        if (find(x) == find(j)) {
                            hasMatched[x-i] = true;
                            //numMatches--;
                            //if (numMatches == 0) break secondSetLoop;
                        }
                        else if (firstSetCostumeVis.contains(find(x))) {
                            continue;
                        }
                        firstSetCostumeVis.add(find(x));
                        System.out.println(2+" "+j+" "+x);
                        System.out.flush();
                        feedBack = Integer.parseInt(br.readLine());
                        if (feedBack == 1) {
                            //numMatches--;
                            unite(x,j);
                            hasMatched[x-i] = true;
                            for (int y = x+1; y <= i+margin/2-1; y++) {
                                if (find(y)==find(x)) {
                                    hasMatched[y-i] = true;
                                }
                            }
                            //if (numMatches == 0) break secondSetLoop;
                            break firstSetLoop;
                        }
                    }
                }
            }
            margin*=2;
        }
        TreeSet<Integer> possCostumes = new TreeSet<>();
        for (int i=1; i <= N; i++) {
            find(i);
            possCostumes.add(father[i]);
        }
        int [] orgToNew = new int [N+1];
        int ind = 1;
        for (int num : possCostumes) {
            orgToNew[num] = ind;
            ind++;
        }
        System.out.print(0+" ");
        for (int i = 1; i <= N; i++) {
            System.out.print(orgToNew[father[i]]+" ");
        }
        System.out.flush();
    }
    static int find (int node) {
        if (father[node] != node) {
            father[node] = find(father[node]);
        }
        return father[node];
    }
    static void unite(int A, int B) {
        int rootA = find(A);
        int rootB = find(B);
        if (height[rootA] > height[rootB]) {
            father[rootB] = rootA;
            height[rootA] = Math.max(height[rootA],height[rootB]+1);
        }
        else {
            father[rootA] = rootB;
            height[rootB] = Math.max(height[rootB],height[rootA]+1);
        }
    }
}

Subtask #1
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 13732 KB Output is correct
2 Correct 482 ms 13740 KB Output is correct
3 Partially correct 826 ms 14004 KB Partially correct
4 Partially correct 854 ms 14272 KB Partially correct
5 Correct 290 ms 13468 KB Output is correct
6 Correct 285 ms 13520 KB Output is correct
7 Correct 431 ms 13540 KB Output is correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 13524 KB Output is correct
2 Correct 455 ms 13768 KB Output is correct
3 Partially correct 571 ms 13816 KB Partially correct
4 Partially correct 901 ms 14248 KB Partially correct
5 Correct 313 ms 13640 KB Output is correct
6 Correct 298 ms 13620 KB Output is correct
7 Correct 363 ms 13520 KB Output is correct

Subtask #3
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 12380 KB Output is correct
2 Correct 344 ms 13540 KB Output is correct
3 Correct 601 ms 13740 KB Output is correct
4 Partially correct 884 ms 14444 KB Partially correct
5 Correct 354 ms 13600 KB Output is correct
6 Correct 368 ms 13648 KB Output is correct
7 Correct 509 ms 13636 KB Output is correct

Subtask #4
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 13556 KB Output is correct
2 Correct 320 ms 13760 KB Output is correct
3 Partially correct 915 ms 14428 KB Partially correct
4 Partially correct 843 ms 14260 KB Partially correct
5 Correct 407 ms 13624 KB Output is correct
6 Correct 552 ms 13720 KB Output is correct
7 Correct 483 ms 13568 KB Output is correct

Subtask #5
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 13592 KB Output is correct
2 Correct 390 ms 13800 KB Output is correct
3 Partially correct 914 ms 14468 KB Partially correct
4 Partially correct 937 ms 14500 KB Partially correct
5 Correct 603 ms 13656 KB Output is correct
6 Partially correct 895 ms 14560 KB Partially correct
7 Partially correct 818 ms 14488 KB Partially correct