Submission #604960

#	Time	Username	Problem	Language	Result	Execution time	Memory
604960		CSQ31	ICC (CEOI16_icc)	C++17	100 / 100	128 ms	508 KiB

icc

#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
int par[1000];
int find(int x){
	if(x==par[x])return x;
	return par[x] = find(par[x]);
}
void unite(int a,int b){
	a = find(a);
	b = find(b);
	if(a==b)return;
	par[a] = b;
	
}
int n;
int A[200],B[200],an,bn;
/*
int query(int a, int b, int *A, int *B){
	int ans;
	for(int i=0;i<a;i++)cout<<A[i]<<" ";
	cout<<'\n';
	for(int i=0;i<b;i++)cout<<B[i]<<" ";
	cout<<'\n';
	cin>>ans;
	return ans;
}
void setRoad(int a, int b){
	cout<<"added edge"<<'\n';
	cout<<a<<" "<<b<<'\n';
}*/
typedef pair<int,int> pii;
#define fi first
#define se second
void run(int N){
	n = N;
	for(int i=1;i<=n;i++)par[i] = i;
	for(int i=1;i<n;i++){
		vector<int>g;
		vector<vector<int>>p(n+1);
		for(int j=1;j<=n;j++){
			if(j==find(j))g.push_back(j);
			p[find(j)].push_back(j);
		}
		vector<int>s1,s2;
		int m = g.size();
		vector<pii>range = {{0,m-1}};
		while(true){
			s1.clear();
			s2.clear();
			vector<pii>rn;
			for(pii x:range){
				int l = x.fi;
				int r = x.se;
				if(l==r)continue;
				int mid = (l+r)/2;
				rn.push_back({l,mid});
				rn.push_back({mid+1,r});
				for(int j=l;j<=mid;j++)s1.push_back(g[j]);
				for(int j=mid+1;j<=r;j++)s2.push_back(g[j]);
			}
			int ptr = 0;
			for(int x:s1){
				for(int y:p[x])A[ptr++] = y;
			}
			an = ptr;
			ptr = 0;
			for(int x:s2){
				for(int y:p[x])B[ptr++] = y;
			}
			bn = ptr;
			if(query(an,bn,A,B))break;
			swap(range,rn);
		}
		int l = 1,r = an;
		while(r>l){
			int mid = (l+r)/2;
			if(query(mid,bn,A,B))r = mid;
			else l = mid+1;
		}
		int v = A[r-1];
		l = 1;r = bn;
		while(r>l){
			int mid = (l+r)/2;
			if(query(an,mid,A,B))r = mid;
			else l = mid+1;
		}
		int u = B[r-1];
		unite(v,u);
		setRoad(v,u);
	}
	
}
/*
int main()
{
	int m;
	cin>>m;
	run(m);
	
}*/

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10