Submission #1009018

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009018		emptypringlescan	카멜레온의 사랑 (JOI20_chameleon)	C++17	64 / 100	36 ms	600 KiB

chameleon

    #include <bits/stdc++.h>
    using namespace std;
    #include "chameleon.h"
    vector<pair<int,int> > eds,adj[1005];
vector<int> st,v;
unordered_set<int> disj[2];
int vis[1005];
void change(int x, int g){
	if(disj[g].find(x)==disj[g].end()) return;
	disj[g].erase(x);
	disj[g^1].insert(x);
	vis[x]=1;
	for(auto i:adj[x]){
		if(!vis[i.first]) change(i.first,g^1);
	}
}
void Solve(int n){
	int x;
	for(int i=1; i<=2*n; i++){
		vector<int> ds;
		for(int j:disj[0]) ds.push_back(j);
		ds.push_back(i);
		x=Query(ds);
		if(x<(int)ds.size()){
			ds.pop_back();
			int lo=0,hi=(int)ds.size(),mid;
			while(lo<hi){
				mid=(lo+hi)/2;
				v.clear();
				v.push_back(i);
				for(int j=lo; j<=mid; j++) v.push_back(ds[j]);
				x=Query(v);
				if(x<(int)v.size()) hi=mid;
				else lo=mid+1;
			}
			if((int)ds.size()>lo){
				eds.push_back({ds[lo],i});
				adj[i].push_back({ds[lo],eds.size()-1});
				adj[ds[lo]].push_back({i,eds.size()-1});
				st.push_back(0);
			}
			
			lo++,hi=(int)ds.size();
			while(lo<hi){
				mid=(lo+hi)/2;
				v.clear();
				v.push_back(i);
				for(int j=lo; j<=mid; j++) v.push_back(ds[j]);
				x=Query(v);
				if(x<(int)v.size()) hi=mid;
				else lo=mid+1;
			}
			if((int)ds.size()>lo){
				eds.push_back({ds[lo],i});
				adj[i].push_back({ds[lo],eds.size()-1});
				adj[ds[lo]].push_back({i,eds.size()-1});
				st.push_back(0);
			}
			
			lo++,hi=(int)ds.size();
			while(lo<hi){
				mid=(lo+hi)/2;
				v.clear();
				v.push_back(i);
				for(int j=lo; j<=mid; j++) v.push_back(ds[j]);
				x=Query(v);
				if(x<(int)v.size()) hi=mid;
				else lo=mid+1;
			}
			if((int)ds.size()>lo){
				eds.push_back({ds[lo],i});
				adj[i].push_back({ds[lo],eds.size()-1});
				adj[ds[lo]].push_back({i,eds.size()-1});
				st.push_back(0);
			}
		}
		
		ds.clear();
		for(int j:disj[1]) ds.push_back(j);
		ds.push_back(i);
		x=Query(ds);
		if(x<(int)ds.size()){
			ds.pop_back();
			int lo=0,hi=(int)ds.size(),mid;
			while(lo<hi){
				mid=(lo+hi)/2;
				v.clear();
				v.push_back(i);
				for(int j=lo; j<=mid; j++) v.push_back(ds[j]);
				x=Query(v);
				if(x<(int)v.size()) hi=mid;
				else lo=mid+1;
			}
			if((int)ds.size()>lo){
				for(int j=0; j<=1000; j++) vis[j]=0;
				change(ds[lo],1);
				eds.push_back({ds[lo],i});
				adj[i].push_back({ds[lo],eds.size()-1});
				adj[ds[lo]].push_back({i,eds.size()-1});
				st.push_back(0);
			}
			
			lo++,hi=(int)ds.size();
			while(lo<hi){
				mid=(lo+hi)/2;
				v.clear();
				v.push_back(i);
				for(int j=lo; j<=mid; j++) v.push_back(ds[j]);
				x=Query(v);
				if(x<(int)v.size()) hi=mid;
				else lo=mid+1;
			}
			if((int)ds.size()>lo){
				for(int j=0; j<=1000; j++) vis[j]=0;
				change(ds[lo],1);
				eds.push_back({ds[lo],i});
				adj[i].push_back({ds[lo],eds.size()-1});
				adj[ds[lo]].push_back({i,eds.size()-1});
				st.push_back(0);
			}
			
			lo++,hi=(int)ds.size();
			while(lo<hi){
				mid=(lo+hi)/2;
				v.clear();
				v.push_back(i);
				for(int j=lo; j<=mid; j++) v.push_back(ds[j]);
				x=Query(v);
				if(x<(int)v.size()) hi=mid;
				else lo=mid+1;
			}
			if((int)ds.size()>lo){
				for(int j=0; j<=1000; j++) vis[j]=0;
				change(ds[lo],1);
				eds.push_back({ds[lo],i});
				adj[i].push_back({ds[lo],eds.size()-1});
				adj[ds[lo]].push_back({i,eds.size()-1});
				st.push_back(0);
			}
		}
		
		disj[1].insert(i);
	}
	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