oj.uz

Submission #270621

# Submission time Handle Problem Language Result Execution time Memory
270621 2020-08-17T20:13:46 Z R3KT Carnival (CEOI14_carnival) Java 11
100 / 100
 235 ms 17448 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<>();
		int[] par = new int[n+1];
		parents.add(1);
		par[1] = 1;
		int counter=2;
		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) {
				parents.add(i);
				par[i] = counter;
				counter++;
			}
			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;
				}
				par[i] = par[parents.get(min)];
			}
		}
		
		StringBuilder sb = new StringBuilder();
		sb.append(0 + " ");
		for (int i=1; i<=n; i++) {
			sb.append(par[i] + " ");
		}
		System.out.println(sb);
		System.exit(0);
	}
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 12924 KB Output is correct
2 Correct 213 ms 15240 KB Output is correct
3 Correct 206 ms 17448 KB Output is correct
4 Correct 151 ms 13896 KB Output is correct
5 Correct 114 ms 12184 KB Output is correct
6 Correct 111 ms 11208 KB Output is correct
7 Correct 171 ms 14180 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 12724 KB Output is correct
2 Correct 197 ms 14668 KB Output is correct
3 Correct 140 ms 13324 KB Output is correct
4 Correct 165 ms 15204 KB Output is correct
5 Correct 161 ms 13180 KB Output is correct
6 Correct 160 ms 13580 KB Output is correct
7 Correct 161 ms 14492 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 10360 KB Output is correct
2 Correct 146 ms 12816 KB Output is correct
3 Correct 235 ms 16652 KB Output is correct
4 Correct 159 ms 15360 KB Output is correct
5 Correct 155 ms 14488 KB Output is correct
6 Correct 176 ms 14168 KB Output is correct
7 Correct 212 ms 14840 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 12676 KB Output is correct
2 Correct 153 ms 13080 KB Output is correct
3 Correct 197 ms 16672 KB Output is correct
4 Correct 148 ms 14496 KB Output is correct
5 Correct 184 ms 14728 KB Output is correct
6 Correct 192 ms 14784 KB Output is correct
7 Correct 203 ms 15608 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 11396 KB Output is correct
2 Correct 186 ms 13736 KB Output is correct
3 Correct 218 ms 16168 KB Output is correct
4 Correct 207 ms 17448 KB Output is correct
5 Correct 179 ms 14528 KB Output is correct
6 Correct 182 ms 16628 KB Output is correct
7 Correct 176 ms 15536 KB Output is correct