Submission #361652

#	Time	Username	Problem	Language	Result	Execution time	Memory
361652		AnythingWithJ	Carnival (CEOI14_carnival)	Java	20 / 100	937 ms	14560 KiB

carnival

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 / 20
• Subtask 2: 4 / 20
• Subtask 3: 4 / 20
• Subtask 4: 4 / 20
• Subtask 5: 4 / 20