Submission #838300

#	Time	Username	Problem	Language	Result	Execution time	Memory
838300		MohamedAhmed04	Chameleon's Love (JOI20_chameleon)	C++14	100 / 100	48 ms	532 KiB

chameleon

#include <bits/stdc++.h>
#include "chameleon.h"

using namespace std ;

const int MAX = 1000 + 10 ;

int n ;
int mark[MAX] ;
vector<int>v[2] ;

vector< vector<int> >adj(MAX) ;

int query(int x , int t , int l , int r)
{
	vector<int>vq = {x} ;
	for(int i = l ; i <= r ; ++i)
		vq.push_back(v[t][i]) ;
	return Query(vq) ;
}

int vis[MAX] , col[MAX] ;

void dfs(int node)
{
	vis[node] = 1 ;
	v[col[node]].push_back(node) ;
	for(auto &child : adj[node])
	{
		if(vis[child])
			continue ;
		col[child] = !col[node] ;
		dfs(child) ;
	}
}

int ans[MAX] ;
int to[MAX] , prv[MAX] ;

void Solve(int N) 
{
	n = N ;
	for(int i = 1 ; i <= 2*n ; ++i)
	{
		for(int j = 0 ; j < 2 ; ++j)
		{
			int sz = v[j].size() , prv = -1 ;
			bool ok = (query(i , j , 0 , sz-1) == sz+1) ;
			while(!ok)
			{
				int l = prv+1 , r = sz-1 ;
				int idx = r ;
				while(l <= r)
				{
					int mid = (l + r) >> 1 ;
					if(query(i , j , prv+1 , mid) != mid-prv+1)
						idx = mid , r = mid-1 ;
					else
						l = mid+1 ;
				}
				adj[i].push_back(v[j][idx]) , adj[v[j][idx]].push_back(i) ;
				prv = idx ;
				ok = (query(i , j , idx+1 , sz-1) == sz-idx) ;
			}
		}
		v[0].clear() , v[1].clear() ;
		memset(vis , 0 , sizeof(vis)) ;
		for(int j = 1 ; j <= i ; ++j)
		{
			if(vis[j])
				continue ;
			col[j] = 0 ;
			dfs(j) ;
		}	
	}
	for(int i = 1 ; i <= 2*n ; ++i)
	{
		assert(adj[i].size() == 1 || adj[i].size() == 3) ;
		if(adj[i].size() == 1)
		{
			ans[i] = adj[i][0] , ans[adj[i][0]] = i ;
			continue ;
		}
		for(int j = 0 ; j < 3 ; ++j)
		{
			for(int k = j+1 ; k < 3 ; ++k)
			{
				vector<int>vq = {i , adj[i][j] , adj[i][k]} ;
				if(Query(vq) == 1)
				{
					int x = adj[i][3 ^ j ^ k] ;
					prv[i] = x , to[x] = i ;
				}
			}
		}
	}
	for(int i = 1 ; i <= 2*n ; ++i)
	{
		if(adj[i].size() != 3)
			continue ;
		for(int j = 0 ; j < 3 ; ++j)
		{
			int x = adj[i][j] ;
			if(to[i] != x && prv[i] != x)
				ans[i] = x , ans[x] = i ;
		}
	}
	for(int i = 1 ; i <= 2*n ; ++i)
	{
		if(ans[i] > i)
			Answer(i , ans[i]) ;
	}
}

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