Submission #1010842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010842		LCJLY	Chameleon's Love (JOI20_chameleon)	C++14	64 / 100	46 ms	600 KiB

chameleon

#include "chameleon.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
	
//#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef array<int,3>pi2;

//Query(vector<int>)
//Answer(int,int)

vector<int>adj[1005];
bool color[1005];
bool visited[1005];

void dfs(int index){
	visited[index]=true;
	//show(visit,index);
	for(auto it:adj[index]){
		if(visited[it]) continue;
		color[it]=color[index]^1;
		dfs(it);
	}
}

pii f(int a, int b){
	return {min(a,b),max(a,b)};
}

void Solve(int n){
	for(int x=1;x<=2*n;x++){
		memset(color,0,sizeof(color));
		memset(visited,0,sizeof(visited));
		for(int y=1;y<x;y++){
			if(!visited[y]){
				dfs(y);
			}
		}
		
		vector<int>v[2];
		for(int y=1;y<x;y++){
			v[color[y]].push_back(y);
		}
		
		int ok=0;
		for(int i=0;i<2;i++){
			//identify all pairs
			int last=0;
			for(int j=0;j<3;j++){
				if(ok==3) break;
				int l=last;
				int r=v[i].size()-1;
				int best=r+1;
				int mid;
				while(l<=r){
					mid=(l+r)/2;
					vector<int>storage;
					for(int k=last;k<=mid;k++){
						storage.push_back(v[i][k]);
					}
					storage.push_back(x);
					int hold=Query(storage);
					if(hold!=(int)storage.size()){
						best=mid;
						r=mid-1;
					}
					else l=mid+1;
				}
				if(best==(int)v[i].size()) break;
				ok++;
				last=best+1;
				adj[x].push_back(v[i][best]);
				adj[v[i][best]].push_back(x);
			}
		}
	}
	
	map<pii,int>mp;
	
	for(int x=1;x<=2*n;x++){
		if(adj[x].size()==1){
			mp[f(x,adj[x][0])]++;
		}
		else if(adj[x].size()==3){
			int hold=Query({x,adj[x][0],adj[x][1]});
			int hold2=Query({x,adj[x][0],adj[x][2]});
			if(hold==1){
				mp[f(x,adj[x][0])]++;
				mp[f(x,adj[x][1])]++;
			}
			else if(hold2==1){
				mp[f(x,adj[x][0])]++;
				mp[f(x,adj[x][2])]++;
			}
			else{
				mp[f(x,adj[x][1])]++;
				mp[f(x,adj[x][2])]++;
			}
		}
	}
	
	for(auto it:mp){
		if(it.second==2){
			//show2(a,it.first.first,b,it.first.second);
			Answer(it.first.first,it.first.second);
		}
	}
}

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