oj.uz

Submission #270403

# Submission time Handle Problem Language Result Execution time Memory
270403 2020-08-17T14:56:36 Z bovinophile Carnival (CEOI14_carnival) Java 11
0 / 100
 189 ms 14088 KB 
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 + 2 + " ");
					// 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.exit(0);
 
	}
 
	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) {
				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.0

# Verdict Execution time Memory Grader output
1 Incorrect 154 ms 13544 KB Integer 19 violates the range [1, 11]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 134 ms 12812 KB Integer 6 violates the range [1, 5]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 10264 KB Output is correct
2 Incorrect 143 ms 13176 KB Integer 11 violates the range [1, 8]
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 132 ms 12684 KB Integer 5 violates the range [1, 4]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 12316 KB Output is correct
2 Incorrect 189 ms 14088 KB Integer 20 violates the range [1, 17]
3 Halted 0 ms 0 KB -