Submission #1009006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009006		emptypringlescan	Chameleon's Love (JOI20_chameleon)	C++17	44 / 100	23 ms	596 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);
    		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);
    		lo=0,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<=500; 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<=500; 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<=500; 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: 0 / 20
• Subtask 5: 0 / 36