Submission #30681

# Submission time Handle Problem Language Result Execution time Memory
30681 2017-07-26T06:03:16 Z zscoder ICC (CEOI16_icc) C++14
0 / 100
0 ms 2048 KB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "icc.h"

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;

static int par[111];
static int ilab[111];
static int lab[111];

static void init(int N)
{
	for(int i = 0; i < N; i++)
	{
		par[i]=i;
	}
}

static int rt(int u)
{
	if(par[u]==u) return u;
	else return (par[u]=rt(par[u]));
}

static void merge(int u, int v)
{
	u=rt(u); v=rt(v);
	if(u==v) return ;
	if(rand()&1) swap(u,v);
	par[v]=u;
}

int relabel(int N)
{
	bool used[111];
	memset(used,0,sizeof(used));
	int cnt=0;
	for(int i = 0; i < N; i++)
	{
		if(!used[par[i]])
		{
			lab[i]=cnt;
			ilab[cnt]=i;
			cnt++;
			used[par[i]]=1;
		}
		else lab[i]=lab[par[i]];
	}
	return cnt;
}

static bool ask(vi &l, vi &r)
{
	if(l.empty()||r.empty()) return 0;
	int L[101]; int R[101];
	/*
	for(int i=0;i<l.size();i++) 
	{
		L[i]=l[i]+1;
		cerr<<l[i]<<' ';
	}
	cerr<<'\n';
	for(int i=0;i<r.size();i++) 
	{
		R[i]=r[i]+1;
		cerr<<r[i]<<' ';
	}
	cerr<<'\n';
	*/
	bool tmp = query(l.size(),r.size(),L,R);
	//cerr<<"RES : "<<tmp<<'\n';
	return tmp;
}

void run(int N)
{
	init(N);
	for(int i = 0; i < N - 1; i++)
	{
		int mx = relabel(N);
		int z = 0;
		while((1<<z)<mx)
		{
			z++;
		}
		int xr = 0;
		for(int i = 0; i < z; i++)
		{
			vi l,r;
			for(int j = 0; j < mx; j++)
			{
				if(j&(1<<i)) l.pb(ilab[j]);
				else r.pb(ilab[j]);
			} 
			if(ask(l,r))
			{
				xr^=(1<<i);
			}
		}
		int a = 0;
		int b = 0;
		int s = 0;
		for(int i=0;i<z;i++) 
		{
			if((xr&(1<<i)))
			{
				s=i;
				break;
			}
		}
		a=(1<<s);
		int mask = (1<<s);
		for(int i = 0; i < z; i++)
		{
			if(i!=s)
			{
				vi L,R;
				for(int j = 0; j < mx; j++)
				{
					if((j&mask)==a&&(j&(1<<i)))
					{
						L.pb(ilab[j]);
					}
				}
				for(int j = 0; j < mx; j++)
				{
					if((j&mask)==b)
					{
						if(xr&(1<<i))
						{
							if(!(j&(1<<i))) R.pb(ilab[j]);
						}
						else
						{
							if((j&(1<<i))) R.pb(ilab[j]);
						}
					}
				}
				if(ask(L,R))
				{
					a^=(1<<i);
					if(!(xr&(1<<i))) b^=(1<<i);
				}
				else
				{
					if((xr&(1<<i))) b^=(1<<i);
				}
				mask^=(1<<i);
			}
		}
		//CC a and CC b are connected
		vi le,ri;
		for(int i=0;i<N;i++)
		{
			if(lab[par[i]]==a) le.pb(i);
			if(lab[par[i]]==b) ri.pb(i);
		}
		/*
		cerr<<"L : ";
		for(int i=0;i<le.size();i++) cerr<<le[i]<<' ';
		cerr<<'\n';
		cerr<<"R : ";
		for(int i=0;i<ri.size();i++) cerr<<ri[i]<<' ';
		cerr<<'\n';
		*/
		int u,v;
		int lo = 0; int hi = int(le.size()) - 1;
		int ans = -1;
		while(lo<=hi)
		{
			if(ans!=-1) break;
			int mid = (lo+hi)>>1;
			if(lo==hi&&ans==-1)
			{
				ans=lo;
				break;
			}
			vi L,R;
			for(int i = lo; i <= mid; i++)
			{
				L.pb(le[i]);
			}
			for(int i = 0; i < ri.size(); i++)
			{
				R.pb(ri[i]);
			}
			if(ask(L,R))
			{
				if(mid==lo)
				{
					ans=mid;
				}
				hi = mid - 1;
			}
			else
			{
				lo = mid + 1;
			}
		}
		u = ans;
		lo = 0; hi = int(ri.size()) - 1;
		ans = -1;
		while(lo<=hi)
		{
			if(ans!=-1) break;
			int mid = (lo+hi)>>1;
			if(lo==hi&&ans==-1)
			{
				ans=lo;
				break;
			}
			vi L,R;
			for(int i = 0; i < le.size(); i++)
			{
				L.pb(le[i]);
			}
			for(int i = lo; i <= mid; i++)
			{
				R.pb(ri[i]);
			}
			if(ask(L,R))
			{
				if(mid==lo)
				{
					ans=mid;
				}
				hi = mid - 1;
			}
			else
			{
				lo = mid + 1;
			}
		}
		v=ans;
		//cerr<<"ANS : "<<le[u]<<' '<<ri[v]<<'\n';
		setRoad(le[u]+1,1+ri[v]);
		merge(le[u],ri[v]);
	}
}

Compilation message

icc.cpp: In function 'void run(int)':
icc.cpp:200:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < ri.size(); i++)
                     ^
icc.cpp:230:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < le.size(); i++)
                     ^
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2048 KB Query cities not in range [1, n]
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2048 KB Query cities not in range [1, n]
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2048 KB Query cities not in range [1, n]
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2048 KB Query cities not in range [1, n]
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2048 KB Query cities not in range [1, n]
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2048 KB Query cities not in range [1, n]
2 Halted 0 ms 0 KB -