oj.uz

Submission #898942

# Submission time Handle Problem Language Result Execution time Memory
898942 2024-01-05T09:30:06 Z LCJLY Carnival (CEOI14_carnival) C++14
100 / 100
 13 ms 708 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 7 ms 448 KB Output is correct
3 Correct 9 ms 456 KB Output is correct
4 Correct 9 ms 696 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 6 ms 604 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 6 ms 452 KB Output is correct
3 Correct 5 ms 448 KB Output is correct
4 Correct 11 ms 452 KB Output is correct
5 Correct 5 ms 452 KB Output is correct
6 Correct 5 ms 456 KB Output is correct
7 Correct 6 ms 448 KB Output is correct

Subtask #3
20.0 / 20.0

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

Subtask #4
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 11 ms 456 KB Output is correct
4 Correct 13 ms 708 KB Output is correct
5 Correct 7 ms 452 KB Output is correct
6 Correct 8 ms 460 KB Output is correct
7 Correct 7 ms 448 KB Output is correct

Subtask #5
20.0 / 20.0

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