Submission #995883

#	Time	Username	Problem	Language	Result	Execution time	Memory
995883		vjudge1	Carnival (CEOI14_carnival)	C++17	100 / 100	16 ms	600 KiB

carnival

#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 (stderr)

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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20