Submission #1057388

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057388		1ne	Carnival (CEOI14_carnival)	C++14	0 / 100	6 ms	344 KiB

carnival

/*
*  author : Apiram                  
*  created: 13.08.2024 23:27:53
*/
 
#include<bits/stdc++.h>
using namespace std;
struct DSU{
	vector<int>parent,sz;
	DSU(int n){
		parent.resize(n);
		sz.resize(n,1);
		iota(parent.begin(),parent.end(),0);
	}
	int findsets(int v){
		if (v == parent[v]){
			return v;
		}
		parent[v] = findsets(parent[v]);
		return parent[v];
	}
	bool unionset(int u,int v){
		u = findsets(u);
		v = findsets(v);
		if (u == v){
			return false;
		}
		if (sz[v] > sz[u]){
			swap(u,v);
		}
		parent[v] = u;
		sz[u]+=sz[v];
		return true;
	};
};
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;cin>>n;
	DSU st(n);
	vector<bool>visited(n,false);
	vector<vector<int>>checked(n + 1,vector<int>(n + 1,-1));
	auto query = [&](int l,int r){
	  if (checked[l][r]!=-1)return checked[l][r];
	  int cnt = 0;
	  for (int i = l;i<=r;++i){
	  	if (!visited[i]){
	  		cnt++;
	  	}
	  }
	  if (cnt <= 1){
	  	return checked[l][r] = 0;		
	  }
	  cout<<cnt;
	  for (int i = l;i<=r;++i){
	 	if (!visited[i]){
	 		cout<<" "<<i + 1;	
	 	} 	
	  }
	  cout<<endl;
	  int a;cin>>a;
	  if (cnt == a)return checked[l][r] = 0;
	  return checked[l][r] = 1;
	};
	for (int i = 0;i<n;++i){
		int left = 0,right = n - 1,pos = -1;
		while(left<=right){
			int mid = (left + right)>>1;
			if (query(i,mid)){
				right = mid - 1;
				pos = mid;	
			}
			else{
				left = mid + 1;
			}
		}
		if (pos == -1)break;
		left = i,right = pos - 1;
		int pos2 = -1;
		while(left<=right){
			int mid = (left + right)>>1;
			if (query(mid,pos)){
				left = mid + 1;
				pos2 = mid;
			}
			else{
				right = mid - 1;
			}
		}
		st.unionset(pos,pos2);
		visited[pos] = true;	
	}
	cout<<0<<" ";
	vector<int>ans;
	for (int i = 0;i<n;++i){
		ans.push_back(st.findsets(i));
	}
	sort(ans.begin(),ans.end());
	ans.erase(unique(ans.begin(),ans.end()),ans.end());
	for (int i = 0;i<n;++i){
		cout<<(lower_bound(ans.begin(),ans.end(),st.findsets(i)) - ans.begin()) + 1<<" ";
	}
	cout<<endl;
	return 0;
}

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