Submission #212013

#	Time	Username	Problem	Language	Result	Execution time	Memory
212013		admin	Chameleon's Love (JOI20_chameleon)	C++14	100 / 100	95 ms	596 KiB

chameleon

#include "chameleon.h"
#include <vector>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
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,int> 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;
 
const double C = 0.5; //might change
int n;
vi L,R;
int solvesingle(vi a, int ele)
{
	assert(!a.empty());
	if(a.size()==1) return a[0];
	//cerr<<"SOLVE SINGLE "<<ele<<" WITH CANDIDATES ";
	//for(int x:a) cerr<<x<<' ';
	//cerr<<'\n';
	while(a.size()>=7)
	{
		int n=a.size();
		int ssiz = max(1,int((n-3)*1.0*C));
		random_shuffle(a.begin(),a.end());
		vector<int> q;
		for(int i=n-1;i>=n-ssiz;i--) q.pb(a[i]);
		q.pb(ele);
		if(Query(q)==q.size())
		{
			for(int i=0;i<ssiz;i++) a.pop_back();
		}
	}
	vi rem;
	for(int i=0;i<a.size();i++)
	{
		if(Query({a[i],ele})!=2)
		{
			rem.pb(a[i]);
		}
	}
	a=rem;
	assert(!a.empty());
	if(a.size()==1) return a[0];
	assert(a.size()<=3); 
	if(a.size()==3)
	{
		for(int i=0;i<=2;i++)
		{
			if(a.size()<=2) break;
			for(int j=i+1;j<=2;j++)
			{
				if(Query({a[i],a[j],ele})==1) 
				{
					a={a[i],a[j]};
					break;
				}
			}
		}
	}
	assert(a.size()==2);
	vi q;
	for(int i=1;i<=2*n;i++)
	{
		if(i==ele||i==a[0])
		{
			continue;
		}
		q.pb(i);
	}
	int r1 = Query(q);
	vi q2;
	for(int i=1;i<=2*n;i++)
	{
		if(i==ele||i==a[1])
		{
			continue;
		}
		q2.pb(i);
	}
	int r2 = Query(q2);
	//cerr<<r1<<' '<<r2<<'\n';
	//assert(r1!=r2);
	if(r1<r2) return a[0];
	else if(r1>r2) return a[1];
	//still here wtf
	q.clear(); q2.clear();
	for(int i=0;i<R.size();i++)
	{
		if(R[i]==ele) continue;
		q.pb(R[i]); q2.pb(R[i]);
	}
	q.pb(a[0]); q2.pb(a[1]);
	r1 = Query(q);
	r2 = Query(q2);
	if(r1>r2) return a[0];
	else if(r1<r2) return a[1];
	assert(0); //nani no crash?
	return a[0];
}
 
void solve2(vi a, vi b)
{
	//for each element in b, find out which element in a it matches to 
	if(a.size()==1) 
	{
		Answer(a[0],b[0]);
		return ;
	}
	random_shuffle(b.begin(),b.end());
	int curele = b.back();
	//how to find the element that matches with curele
	int matchele = solvesingle(a,curele);
	for(int i=0;i<a.size();i++)
	{
		if(a[i]==matchele)
		{
			a.erase(a.begin()+i); break;
		}
	}
	b.pop_back();
	Answer(curele,matchele);
	solve2(a,b);
}
 
bool ban[22222];
int color[2222];
vi adj[2222];
int queries=0;
void dfs(int u)
{
	for(int i:adj[u])
	{
		if(color[i]==0)
		{
			color[i]=color[u]^1;
			dfs(i);
		}
	}
}
 
const int ITER = 100;
const double PROB = 0.5;
 
double rndp()
{
	return ld(rand()%10000)/10000.0;
}
 
int like[2222];
int liked[2222];
void Solve(int N) 
{
	n=N;
	srand(129138);
	for(int i=2;i<=2*N;i++)
	{
		memset(color,0,sizeof(color));
		for(int j=1;j<i;j++)
		{
			if(color[j]==0)
			{
				color[j]=2;
				dfs(j);
			}
		}
		deque<int> S[2];
		for(int j=1;j<i;j++)
		{
			S[color[j]&1].pb(j);
		}
		for(int z=0;z<2;z++)
		{
			while(adj[i].size()<3&&S[z].size()>0)
			{
				S[z].pb(i);
				vi ss;
				for(int s:S[z]) ss.pb(s);
				if(Query(ss)==S[z].size()) break;
				S[z].pop_back();
				int lo=0; int hi=int(S[z].size())-1;
				int ans=S[z].size();
				while(lo<=hi)
				{
					int mid=(lo+hi)>>1;
					vi q;
					for(int i=0;i<=mid;i++)
					{
						q.pb(S[z][i]);
					}
					q.pb(i);
					if(Query(q)<q.size())
					{
						ans=mid;
						hi=mid-1;
					}
					else lo=mid+1;
				}
				if(ans<S[z].size())
				{
					adj[i].pb(S[z][ans]);
					adj[S[z][ans]].pb(i);
				}
				for(int i=0;(i<=ans&&(!S[z].empty()));i++) S[z].pop_front();
			}
		}
	}
	cerr<<queries<<'\n';
	memset(color,0,sizeof(color));
	for(int i=1;i<=2*N;i++)
	{
		if(color[i]==0)
		{
			color[i]=2;
			dfs(i);
		}
	}
	for(int i=1;i<=2*N;i++)
	{
		sort(adj[i].begin(),adj[i].end());
		adj[i].erase(unique(adj[i].begin(),adj[i].end()),adj[i].end());
		if(adj[i].size()>1)
		{
			assert(adj[i].size()==3);
			if(Query({i,adj[i][0],adj[i][1]})==1) like[i]=adj[i][2];
			else if(Query({i,adj[i][0],adj[i][2]})==1) like[i]=adj[i][1];
			else like[i]=adj[i][0];
		}
	}
	for(int i=1;i<=2*N;i++)
	{
		liked[like[i]]=i;
	}
	for(int i=1;i<=2*N;i++)
	{
		int ans=0;
		for(int v:adj[i])
		{
			if(v==like[i]||v==liked[i]) continue;
			ans=v; break;
		}
		if(ans>i) Answer(i,ans);
	}
	/*
	int queries=0;
	vi tmpban;
	while(curset.size()<N)
	{
		curset.pb(cur.back());
		int tmp = Query(curset);
		if(tmp>=curset.size())
		{
			cur.pop_back();
			continue;
		}
		curset.pop_back();
		random_shuffle(cur.begin(),cur.end());
		random_shuffle(curset.begin(),curset.end());
		bool pos=0;
		for(int i=0;i<cur.size();i++)
		{
			curset.pb(cur[i]);
			int tmp = Query(curset);
			if(tmp>=curset.size())
			{
				cur.erase(cur.begin()+i);
				pos=1; break;
			}
			curset.pop_back();
		}
		if(pos) continue;
		cur.pb(curset.back());
		curset.pop_back();
	}
	*/
}

Compilation message (stderr)

chameleon.cpp: In function 'int solvesingle(vi, int)':
chameleon.cpp:41:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(Query(q)==q.size())
      ~~~~~~~~^~~~~~~~~~
chameleon.cpp:47:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a.size();i++)
              ~^~~~~~~~~
chameleon.cpp:100:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<R.size();i++)
              ~^~~~~~~~~
chameleon.cpp: In function 'void solve2(vi, vi)':
chameleon.cpp:126:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a.size();i++)
              ~^~~~~~~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:191:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(Query(ss)==S[z].size()) break;
        ~~~~~~~~~^~~~~~~~~~~~~
chameleon.cpp:204:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if(Query(q)<q.size())
         ~~~~~~~~^~~~~~~~~
chameleon.cpp:211:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(ans<S[z].size())
        ~~~^~~~~~~~~~~~

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