oj.uz

Submission #992699

# Submission time Handle Problem Language Result Execution time Memory
992699 2024-06-05T04:07:20 Z aaargh Carnival (CEOI14_carnival) C++17
100 / 100
 9 ms 688 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define nl '\n'
// #define io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define pii pair<int,int>

int query(int n, vector<int> people) {
	cout << n;
	for (int i = 0; i < n; i++) {
		cout << " " << people[i]; 
	}
	cout << endl;
	int temp;
	cin >> temp;
	return temp;
} 

void output(vector<int> v) {
	cout << 0;
	for (int e: v) cout << " " << e;
	cout << endl;
}

signed main() {
	// io;
	int n; cin >> n;
	vector<int> unique;
	unique.push_back(1);
	vector<int> costumes; 
	costumes.push_back(1);
	int prev, temp, temp2, temp3;
	//vector<int> nums;
	//nums.push_back(1);
	int maxcost = 1; 
	prev = 1;
	for (int i = 1; i < n; i++) {
		// first one is always unique
		unique.push_back(i+1);
		temp = query(unique.size(), unique);
		if (temp == prev+1) {
			// unique.push_back()
			// keep it in unique and add to costumes
			costumes.push_back(maxcost+1);
			maxcost++;
		} else {
			unique.pop_back();
			// check which one it is the same as
			int l = 0, r = unique.size()-1;
			int mid;

			while (r - l >= 1) {
				// cerr << "hi" << nl;
				mid = (l+r)/2;
				// query lower range if in or not
				vector<int> v(unique.begin()+l, unique.begin()+mid+1);
				temp2 = query(mid-l+1, v); // 0 to mid-1
				v.push_back(i+1);
				temp3 = query(mid-l+2, v);
				if (temp2  == temp3) {
					r = mid; // it could be in l to mid inclusive
				} else {
					l = mid+1; // it could be in mid+1 to r
				}
			}
			mid = (l+r)/2;
			// cout << "mid is " << unique[mid];
			costumes.push_back(costumes[unique[mid]-1]);

		}
		prev = temp;
	}
	output(costumes);
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 5 ms 344 KB Output is correct
3 Correct 5 ms 452 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 2 ms 344 KB Output is correct
7 Correct 6 ms 344 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 9 ms 344 KB Output is correct
3 Correct 3 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 6 ms 344 KB Output is correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 5 ms 440 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 6 ms 444 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 6 ms 688 KB Output is correct
7 Correct 7 ms 440 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 7 ms 340 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 8 ms 344 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 600 KB Output is correct
2 Correct 9 ms 436 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 4 ms 444 KB Output is correct
5 Correct 5 ms 344 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 2 ms 344 KB Output is correct