제출 #1009033

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1009033		emptypringlescan	카멜레온의 사랑 (JOI20_chameleon)	C++17	0 / 100	0 ms	344 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();
			v.clear();
			for(int j=lo; j<hi; j++) v.push_back(ds[j]);
			v.push_back(i);
			if(Query(v)<(int)v.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();
				v.clear();
				for(int j=lo; j<hi; j++) v.push_back(ds[j]);
				v.push_back(i);
				if(Query(v)<(int)v.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();
			v.clear();
			for(int j=lo; j<hi; j++) v.push_back(ds[j]);
			v.push_back(i);
			if(Query(v)<(int)v.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();
				v.clear();
				for(int j=lo; j<hi; j++) v.push_back(ds[j]);
				v.push_back(i);
				if(Query(v)<(int)v.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<=8; i++){
		cout << i << ": ";
		for(auto [j,k]:adj[i]){
			cout << j << ' ';
		}
		cout << '\n';
	}
	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: 0 / 4
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36