oj.uz

Submission #1057396

# Submission time Handle Problem Language Result Execution time Memory
1057396 2024-08-13T18:43:31 Z 1ne Carnival (CEOI14_carnival) C++14
100 / 100
 9 ms 688 KB 
/*
*  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 = i - 1,pos = -1;
		while(left<=right){
			int mid = (left + right)>>1;
			if (query(mid,i)){
				left = mid + 1;
				pos = mid;
			}
			else{
				right = mid - 1;
			}
		}
		if (pos == -1)continue;
		st.unionset(pos,i);
		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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 3 ms 344 KB Output is correct
3 Correct 4 ms 536 KB Output is correct
4 Correct 7 ms 344 KB Output is correct
5 Correct 6 ms 344 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 5 ms 600 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 4 ms 460 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 5 ms 540 KB Output is correct
5 Correct 4 ms 600 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 5 ms 540 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 528 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 9 ms 544 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 3 ms 548 KB Output is correct
7 Correct 4 ms 600 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 5 ms 688 KB Output is correct
4 Correct 7 ms 344 KB Output is correct
5 Correct 6 ms 544 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 4 ms 344 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 5 ms 344 KB Output is correct
5 Correct 4 ms 600 KB Output is correct
6 Correct 6 ms 540 KB Output is correct
7 Correct 6 ms 344 KB Output is correct