oj.uz

Submission #212003

# Submission time Handle Problem Language Result Execution time Memory
212003 2020-03-22T00:59:47 Z zscoder Chameleon's Love (JOI20_chameleon) C++17
44 / 100
 124 ms 616 KB 
#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(S[z].size()>0)
			{
				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();
			}
		}
	}
	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);
			for(int j=0;j<2;j++)
			{
				for(int k=j+1;k<3;k++)
				{
					if(Query({i,adj[i][j],adj[i][k]})==1)
					{
						for(int z=0;z<3;z++)
						{
							if(z!=j&&z!=k) like[i]=adj[i][z];
						}
						break;
					}
				}
			}
		}
	}
	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

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:199:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if(Query(q)<q.size())
         ~~~~~~~~^~~~~~~~~
chameleon.cpp:206:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(ans<S[z].size())
        ~~~^~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 96 ms 480 KB Output is correct
4 Correct 95 ms 496 KB Output is correct
5 Correct 105 ms 476 KB Output is correct
6 Correct 115 ms 480 KB Output is correct
7 Correct 109 ms 616 KB Output is correct
8 Correct 124 ms 480 KB Output is correct
9 Correct 106 ms 476 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 7 ms 392 KB Output is correct
11 Correct 6 ms 460 KB Output is correct
12 Correct 7 ms 432 KB Output is correct
13 Correct 6 ms 384 KB Output is correct
14 Correct 6 ms 384 KB Output is correct
15 Correct 7 ms 384 KB Output is correct
16 Correct 6 ms 384 KB Output is correct
17 Correct 6 ms 512 KB Output is correct
18 Correct 7 ms 436 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Incorrect 84 ms 460 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 96 ms 480 KB Output is correct
4 Correct 95 ms 496 KB Output is correct
5 Correct 105 ms 476 KB Output is correct
6 Correct 115 ms 480 KB Output is correct
7 Correct 109 ms 616 KB Output is correct
8 Correct 124 ms 480 KB Output is correct
9 Correct 106 ms 476 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 7 ms 392 KB Output is correct
20 Correct 6 ms 460 KB Output is correct
21 Correct 7 ms 432 KB Output is correct
22 Correct 6 ms 384 KB Output is correct
23 Correct 6 ms 384 KB Output is correct
24 Correct 7 ms 384 KB Output is correct
25 Correct 6 ms 384 KB Output is correct
26 Correct 6 ms 512 KB Output is correct
27 Correct 7 ms 436 KB Output is correct
28 Correct 5 ms 384 KB Output is correct
29 Correct 5 ms 384 KB Output is correct
30 Incorrect 84 ms 460 KB Wrong Answer [3]
31 Halted 0 ms 0 KB -