Submission #268738

#	Time	Username	Problem	Language	Result	Execution time	Memory
268738		R3KT	Carnival (CEOI14_carnival)	Java	0 / 100	98 ms	10360 KiB

carnival

import java.util.*;
import java.io.*;

public class carnival {

	// https://oj.uz/problem/view/CEOI14_carnival
	
	public static void main(String[] args) throws IOException, FileNotFoundException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(in.readLine());

		ArrayList<Integer> parents = new ArrayList<>();
		parents.add(1);
		DSU dsu = new DSU(n+1);
		dsu.MakeSet(1);
		for (int i=2; i<=n; i++) {
			StringBuilder sb = new StringBuilder();
			sb.append(parents.size()+1 + " ");
			for (int j=0; j<parents.size(); j++) {
				sb.append(parents.get(j) + " ");
			}
			sb.append(i + " ");
			System.out.println(sb);
			System.out.flush();
			int curvalue = Integer.parseInt(in.readLine());
			if (curvalue == parents.size()+1) {
				dsu.MakeSet(i);
				parents.add(i);
			}
			else {
				// binary search where it needs to go
				int min=0;
				int max = parents.size()-1;
				while (min < max) {
					int middle = (min + max)/2;
					sb = new StringBuilder();
					sb.append(middle - min + 1 + " ");
					// search first half
					for (int j=min; j<=middle; j++) {
						sb.append(parents.get(j) +  " ");
					}
					sb.append(i + " ");
					System.out.println(sb);
					System.out.flush();
					int curvalue2 = Integer.parseInt(in.readLine());
					if (curvalue2 == middle-min+1) {
						// inside lower half
						max = middle;
					}
					else min = middle+1;
				}
				dsu.Union(parents.get(min), i);
			}
		}
		
		StringBuilder sb = new StringBuilder();
		sb.append(0 + " ");
		for (int i=1; i<=n; i++) {
			sb.append(dsu.parent.get(i) + " ");
		}
		System.out.println(sb);
		System.out.flush();

	}
	
	static class DSU {
		int n;
		ArrayList<Integer> parent;
		ArrayList<Integer> size;
		
		DSU (int n) {
			this.n = n;
			parent = new ArrayList<>();
			size = new ArrayList<>();
			for (int i=0; i<n; i++) {parent.add(i); size.add(1);}
		}
		
		public void MakeSet(int a) {
			parent.add(a);
			size.add(1);
		}
		
		public int FindSet(int a) {
			if (a == parent.get(a)) return a;
			parent.set(a, FindSet(parent.get(a)));
			return parent.get(a);
		}
		
		public void Union(int a, int b) {
			a = FindSet(a);
			b = FindSet(b);
			// if (a == b) { } // cycle found
			if (a != b) {
				if (size.get(a) < size.get(b)) {
					parent.set(a, b);
					size.set(b, size.get(b) + size.get(a));
				}
				else {
					parent.set(b, a);
					size.set(a, size.get(b) + size.get(a));
				}
			}
		}
	}
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20