oj.uz

Submission #931931

# Submission time Handle Problem Language Result Execution time Memory
931931 2024-02-22T15:28:21 Z OAleksa Carnival (CEOI14_carnival) C++14
100 / 100
 10 ms 968 KB 
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	int n;
  	cin >> n;
  	vector<int> vis(n), ans(n);
  	auto Ask = [&](vector<int> s) {
  		cout << s.size() << ' ';
  		for (auto i : s)
  			cout << i + 1 << ' ';
  		cout << endl;
  		int r;
  		cin >> r;
  		return r;
  	};
  	vis[0] = 1;
  	vector<int> s, c;
  	for (int i = 0;i < n;i++)
  		s.push_back(i);
  	int C = Ask(s);
  	s.clear();
  	c.push_back(0);
  	vis[0] = 1;
  	for (int i = 1;i < C;i++) {
  		int l = 0, r = n - 1, id = -1;
  		while (l <= r) {
  			int mid = (l + r) / 2;
  			s.clear();
  			for (auto j : c)
  				s.push_back(j);
  			for (int j = 0;j <= mid;j++) {
  				if (!vis[j])
  					s.push_back(j);
  			}
  			sort(s.begin(), s.end());
  			if (Ask(s) > i)	 {
  				r = mid - 1;
  				id = mid;
  			}
  			else
  				l = mid + 1;
  		}
  		assert(id != -1);
  		vis[id] = 1;
  		c.push_back(id);
  	}
  	for (int i = 0;i < C;i++)
  		ans[c[i]] = i + 1;
  	for (int i = 0;i < n;i++) {
  		if (!vis[i]) {
  			int l = 0, r = C - 1, id = -1;
  			while (l <= r) {
  				int mid = (l + r) / 2;
  				vector<int> s;
  				s.push_back(i);
  				for (int j = 0;j <= mid;j++)
  					s.push_back(c[j]);
  				sort(s.begin(), s.end());
  				if (Ask(s) == mid + 1) {
  					id = mid;
  					r = mid - 1;
  				}
  				else
  					l = mid + 1;
  			}
  			assert(id != -1);
  			ans[i] = ans[c[id]];
  		}
  	}
  	cout << "0 ";
  	for (int i = 0;i < n;i++)
  		cout << ans[i] << ' ';
  	cout << endl;
  }
  return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
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 456 KB Output is correct
4 Correct 8 ms 456 KB Output is correct
5 Correct 3 ms 452 KB Output is correct
6 Correct 3 ms 456 KB Output is correct
7 Correct 3 ms 456 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 2 ms 344 KB Output is correct
3 Correct 6 ms 712 KB Output is correct
4 Correct 8 ms 460 KB Output is correct
5 Correct 4 ms 460 KB Output is correct
6 Correct 5 ms 456 KB Output is correct
7 Correct 5 ms 716 KB Output is correct

Subtask #4
20.0 / 20.0

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

Subtask #5
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 9 ms 452 KB Output is correct
4 Correct 8 ms 708 KB Output is correct
5 Correct 8 ms 464 KB Output is correct
6 Correct 9 ms 716 KB Output is correct
7 Correct 9 ms 460 KB Output is correct