Submission #898942

#	Time	Username	Problem	Language	Result	Execution time	Memory
898942		LCJLY	Carnival (CEOI14_carnival)	C++14	100 / 100	13 ms	708 KiB

carnival

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl; 
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;
typedef pair<int,int>pii;
//typedef pair<int,pii>pi2;
typedef array<int,4>pi2;

struct DSU{
	vector<int>e;
	void init(int n){
		e=vector<int>(n,-1);
	}
	
	int get(int x){return e[x]<0?x:e[x]=get(e[x]);}
	
	bool unite(int x, int y){
		x=get(x);
		y=get(y);
		if(x==y) return 0;
		if(e[x]>e[y]) swap(x,y);
		e[x]+=e[y];
		e[y]=x;
		return 1;
	}
};

void solve(){	
	int n;
	cin >> n;
	
	DSU dsu;
	dsu.init(n+5);

	for(int x=n-1;x>=1;x--){
		int l=x;
		int r=n;
		int best=n+1;
		int mid;
		while(l<=r){
			mid=(l+r)/2;
			set<int>se;
			cout << mid-x+1 << " ";
			for(int y=x;y<=mid;y++){
				se.insert(dsu.get(y));
				cout << y << " ";
			}
			cout << endl;
			
			int hold;
			cin >> hold;
			
			if(hold<(int)se.size()){
				best=mid;
				r=mid-1;
			}
			else l=mid+1;
		}
		
		if(best!=n+1){
			dsu.unite(x,best);
		}
	}
	
	cout << 0 << " ";
	vector<int>v;
	for(int x=1;x<=n;x++){
		if(dsu.get(x)==x) v.push_back(x);
	}
	
	for(int x=1;x<=n;x++){
		int hold=dsu.get(x);
		cout << lower_bound(v.begin(),v.end(),hold)-v.begin()+1 << " ";
	}
	cout << endl;
}
 
int32_t main(){										
	ios::sync_with_stdio(0);	
	cin.tie(0);
	//freopen("redistricting.in", "r", stdin);
	//freopen("redistricting.out", "w", stdout);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}	
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20