oj.uz

답안 #1057372

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1057372 2024-08-13T18:27:29 Z 1ne 사육제 (CEOI14_carnival) C++14
0 / 100
 0 ms 452 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);
	auto query = [&](int l,int r){
	  int cnt = 0;
	  vector<int>pos;
	  for (int i = l;i<=r;++i){
	  	if (!visited[i]){
	  		cnt++;
	  		pos.push_back(i);
	  	}
	  }
	  if (cnt <= 1){
	  	return 0;		
	  }
	  for (int i = 0;i<(int)pos.size();++i){
	 	if (i == 0){
	 		cout<<pos[i] + 1;
	 	} 	
	 	else{
	 		cout<<" "<<pos[i] + 1;
	 	}
	  }
	  cout<<endl;
	  int a;cin>>a;
	  if (cnt == a)return 0;
	  return 1;
	};
	for (int i = 0;i<n;++i){
		int left = i + 1,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);	
	}
	cout<<0;
	for (int i = 0;i<n;++i){
		cout<<" "<<st.findsets(i) + 1;
	}
	cout<<endl;
	return 0;
}

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 344 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 344 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 344 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 344 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 452 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -