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(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);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
362 ms |
14132 KB |
Integer 42 violates the range [1, 11] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
328 ms |
13528 KB |
Integer 94 violates the range [1, 5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
243 ms |
12356 KB |
Integer 94 violates the range [1, 1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
319 ms |
13584 KB |
Integer 78 violates the range [1, 4] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
308 ms |
13536 KB |
Integer 89 violates the range [1, 2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
