Submission #1008929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008929		emptypringlescan	Chameleon's Love (JOI20_chameleon)	C++17	64 / 100	15 ms	552 KiB

chameleon

#include <bits/stdc++.h>
using namespace std;
#include "chameleon.h"
void Solve(int n){
	if(n<=50){
		vector<pair<int,int> > eds,adj[2*n+1];
		vector<int> st;
		for(int i=1; i<2*n; i++){
			for(int j=i+1; j<=2*n; j++){
				int x=Query({i,j});
				if(x==1){
					eds.push_back({i,j});
					adj[i].push_back({j,eds.size()-1});
					adj[j].push_back({i,eds.size()-1});
					st.push_back(0);
				}
			}
		}
		for(int i=1; i<=2*n; i++){
			if((int)adj[i].size()==1) continue;
			assert((int)adj[i].size()==3);
			int a=Query({i,adj[i][0].first,adj[i][1].first});
			int b=Query({i,adj[i][0].first,adj[i][2].first});
			int c=Query({i,adj[i][1].first,adj[i][2].first});
			if(a==1) st[adj[i][2].second]=1;
			if(b==1) st[adj[i][1].second]=1;
			if(c==1) st[adj[i][0].second]=1;
		}
		for(int i=0; i<(int)eds.size(); i++){
			if(st[i]==0) Answer(eds[i].first,eds[i].second);
		}
	}
	else{
		vector<int> v;
		int got[2*n+1];
		memset(got,0,sizeof(got));
		bool st1=false;
		for(int i=1; i<=2*n; i++){
			if(i>n&&!st1) break;
			v.clear();
			for(int j=1; j<=i; j++) if(!got[j]) v.push_back(j);
			int x=Query(v);
			if(x<(int)v.size()){
				if(i<=n) st1=true;
				int lo=1,hi=i-1,mid;
				while(lo<hi){
					mid=(lo+hi)/2;
					v.clear();
					v.push_back(i);
					for(int j=lo; j<=mid; j++) if(!got[j]) v.push_back(j);
					x=Query(v);
					if(x<(int)v.size()) hi=mid;
					else lo=mid+1;
				}
				Answer(lo,i);
				got[lo]=1;
				got[i]=1;
			}
		}
		if(!st1){
			vector<pair<int,int> > eds,adj[2*n+1];
			vector<int> st;
			int x;
			for(int i=n+1; i<=2*n; i++){
				int lo=1,hi=n,mid;
				while(lo<hi){
					mid=(lo+hi)/2;
					v.clear();
					v.push_back(i);
					for(int j=lo; j<=mid; j++) v.push_back(j);
					x=Query(v);
					if(x<(int)v.size()) hi=mid;
					else lo=mid+1;
				}
				eds.push_back({lo,i});
				adj[i].push_back({lo,eds.size()-1});
				adj[lo].push_back({i,eds.size()-1});
				st.push_back(0);
				
				lo++,hi=n+1;
				while(lo<hi){
					mid=(lo+hi)/2;
					v.clear();
					v.push_back(i);
					for(int j=lo; j<=mid; j++) v.push_back(j);
					x=Query(v);
					if(x<(int)v.size()) hi=mid;
					else lo=mid+1;
				}
				if(lo==n+1) continue;
				eds.push_back({lo,i});
				adj[i].push_back({lo,eds.size()-1});
				adj[lo].push_back({i,eds.size()-1});
				st.push_back(0);
				
				lo++,hi=n+1;
				while(lo<hi){
					mid=(lo+hi)/2;
					v.clear();
					v.push_back(i);
					for(int j=lo; j<=mid; j++) v.push_back(j);
					x=Query(v);
					if(x<(int)v.size()) hi=mid;
					else lo=mid+1;
				}
				if(lo==n+1) continue;
				eds.push_back({lo,i});
				adj[i].push_back({lo,eds.size()-1});
				adj[lo].push_back({i,eds.size()-1});
				st.push_back(0);
			}
			for(int i=1; i<=2*n; i++){
				if((int)adj[i].size()==1) continue;
				assert((int)adj[i].size()==3);
				int a=Query({i,adj[i][0].first,adj[i][1].first});
				int b=Query({i,adj[i][0].first,adj[i][2].first});
				int c=Query({i,adj[i][1].first,adj[i][2].first});
				if(a==1) st[adj[i][2].second]=1;
				if(b==1) st[adj[i][1].second]=1;
				if(c==1) st[adj[i][0].second]=1;
			}
			for(int i=0; i<(int)eds.size(); i++){
				if(st[i]==0) Answer(eds[i].first,eds[i].second);
			}
		}
	}
}

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