oj.uz

Submission #995883

# Submission time Handle Problem Language Result Execution time Memory
995883 2024-06-10T03:22:48 Z vjudge1 Carnival (CEOI14_carnival) C++17
100 / 100
 16 ms 600 KB 
#include<bits/stdc++.h>
#define all(x) (x).begin() , (x).end()
#define pll pair<long long, long long>
#define pii pair<int , int>
#define fi first
#define se second
#define bit(i,j) ((j >> i) & 1)
using namespace std;

const long long inf = 1e18;
const int mod = 998244353;
const int MAXN = 2e5+100;

#define int long long

int par[MAXN];
int find(int x){
	if(x == par[x]) return x;
	return par[x] = find(par[x]);
}
void joint(int u , int v){
	u = find(u) , v = find(v);
	if(u != v) par[u] = v;
}
int32_t main(){
  	//freopen("cbarn.in", "r", stdin);
	//freopen("cbarn.out", "w", stdout);
	ios_base::sync_with_stdio(0); cin.tie(0);

	int n; cin >> n;
	vector<int> p(n+1);
	for(int i = 1 ; i <= n ; i++) par[i] = i;
	for(int i = 1 ; i <= n-1 ; i++){
		int l = i + 1 , r = n;
		int res = -1;
		while(l <= r){
			int mid = l + r >> 1;
			int t1 , t2;
			cout << mid - i + 1 << " ";
			for(int j = i ; j <= mid ; j++) cout << j << " ";
			cout << endl;
			cin >> t1;
			cout << mid - i << " ";
			for(int j = i + 1; j <= mid ; j++) cout << j << " ";
			cout << endl;
			cin >> t2;
			if(t1 == t2) res = mid , r = mid-1;
			else l = mid+1;
		}
		p[i] = res;
	}
	for(int i = 1 ; i <= n ; i++){
		if(p[i] > 0) joint(i , p[i]);
	}
	vector<int> cnt(n+1);
	for(int i = 1 ; i <= n ; i++) cnt[find(i)] = 1;
	int c = 1;
	for(int i = 1 ; i <= n ; i++){
		if(cnt[i] == 1) cnt[i] = c , c++;
	}
	cout << 0 << " ";
	for(int i = 1 ; i <= n ; i++) cout << cnt[find(i)] << " ";
	cout << endl;

	return 0;
}

Compilation message

carnival.cpp: In function 'int32_t main()':
carnival.cpp:37:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |    int mid = l + r >> 1;
      |              ~~^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 9 ms 344 KB Output is correct
3 Correct 16 ms 456 KB Output is correct
4 Correct 12 ms 344 KB Output is correct
5 Correct 11 ms 456 KB Output is correct
6 Correct 7 ms 600 KB Output is correct
7 Correct 10 ms 456 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 464 KB Output is correct
2 Correct 9 ms 344 KB Output is correct
3 Correct 9 ms 344 KB Output is correct
4 Correct 16 ms 436 KB Output is correct
5 Correct 6 ms 344 KB Output is correct
6 Correct 11 ms 460 KB Output is correct
7 Correct 8 ms 340 KB Output is correct

Subtask #3
20.0 / 20.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 452 KB Output is correct
2 Correct 7 ms 344 KB Output is correct
3 Correct 13 ms 596 KB Output is correct
4 Correct 15 ms 344 KB Output is correct
5 Correct 11 ms 436 KB Output is correct
6 Correct 10 ms 344 KB Output is correct
7 Correct 12 ms 592 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 592 KB Output is correct
2 Correct 9 ms 344 KB Output is correct
3 Correct 12 ms 344 KB Output is correct
4 Correct 14 ms 592 KB Output is correct
5 Correct 11 ms 444 KB Output is correct
6 Correct 12 ms 344 KB Output is correct
7 Correct 16 ms 452 KB Output is correct