Submission #520045

#	Time	Username	Problem	Language	Result	Execution time	Memory
520045		nathanlee726	Chameleon's Love (JOI20_chameleon)	C++14	100 / 100	53 ms	576 KiB

chameleon

//#include<i_am_noob_orz>
#include<bits/stdc++.h>
#include "chameleon.h"
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
//#define int ll
#define ull unsigned long long
#define pii pair<int,int>
#define X first
#define Y second
#define mod ((ll)1e9+7)
#define pb push_back
#define mp make_pair
#define abs(x) ((x)>0?(x):(-(x)))
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define memres(a) memset(a,0,sizeof(a))
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define endl '\n'
#define bit_count(x) __builtin_popcountll((x))
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define jimmy_is_kind false
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
 
//#define LOCAL
#ifdef LOCAL
#define bug(...) cerr<<"#"<<__LINE__<<' '<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios_base::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif
 
int add(int a,int b){return(a+b>=mod?a+b-mod:a+b);}
int sub(int a,int b){return(a<b?a+mod-b:a-b);}
int po(int a,int b){
	if(b==0)return 1;
	if(b==1)return(a%mod);
	int tem=po(a,b/2);
	if(b&1)return(((tem*tem)%mod)*a)%mod;
	else return(tem*tem)%mod; 
}
int GCD(int a,int b){
	int x=0;
	int ra,rb;
	while(a&&b){
		if(((a&1)==0)&&((b&1)==0)){
			a>>=1,b>>=1,x++;
		}
		else if((a^b)&1){
			if(a&1)b>>=1;
			else a>>=1;
		}
		else{
			ra=abs(a-b),rb=min(a,b);
			a=ra,b=rb;
		}
	}
	return max(a,b)<<x;
}
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}

#ifdef LOCAL
int Query(vector<int> &v){for(int i:v)cout<<i<<" ";cout<<endl;return 0;}
void Answer(int x,int y){}
#endif

int n,gr[1005];
bool vis[1005];
vector<int> g[1005],tv,rg[1005];
 
void dfs(int p,int ty){
	vis[p]=1;
	gr[p]=ty;
	for(int u:g[p]){
		if(!vis[u])dfs(u,1-ty);
	}
}

void fd_ed(int x){
	Fi(ti,3){
		if(sz(tv)==0)return;
		tv.pb(x+1);
		int re=Query(tv);
		int y;
		if(re!=sz(tv)){
			//assert(re==sz(tv)-1);
			vector<int> ttv;
			F(sz(tv)-1)ttv.pb(tv[i]);
			while(sz(ttv)>1){
				int mi=(sz(ttv)/2);
				vector<int> tttv;
				F(mi)tttv.pb(ttv[i]);
				tttv.pb(x+1);
				int re=Query(tttv);
				if(re!=sz(tttv)){
					tttv.pop_back();
				}
				else{
					tttv.clear();
					for(int i=mi;i<sz(ttv);i++)tttv.pb(ttv[i]);
				}
				swap(tttv,ttv);
			}
			assert(sz(ttv)==1);
			g[x].pb(ttv[0]-1);
			g[ttv[0]-1].pb(x); 
			y=ttv[0];
		}
		else{
			return;
		}
		tv.pop_back();
		vector<int> ttv;
		for(int i:tv){
			if(i!=y)ttv.pb(i);
		}
		swap(tv,ttv);
	}
}

void Solve(int N){
	n=N*2;
	F(n){
		memres(vis);
		Fi(j,i){
			if(!vis[j])dfs(j,0);
		}
		tv.clear();
		Fi(j,i){
			if(gr[j]==0)tv.pb(j+1);
		}
			if(sz(tv)!=0){
				fd_ed(i);	
			}
		tv.clear();
		Fi(j,i){
			if(gr[j]==1)tv.pb(j+1);
			
		}
		if(sz(tv)!=0){
				fd_ed(i);	
			}
	}
	F(n){ 
		if(sz(g[i])==3){
			vector<int> v1,v2;
			v1.pb(i+1);v1.pb(g[i][0]+1);v1.pb(g[i][1]+1);
			v2.pb(i+1);v2.pb(g[i][0]+1);v2.pb(g[i][2]+1);
			if(Query(v1)==1){
				rg[i].pb(g[i][2]);
				rg[g[i][2]].pb(i);
			}
			else if(Query(v2)==1){
				rg[i].pb({g[i][1]});
				rg[g[i][1]].pb(i);
			}
			else{
				rg[i].pb({g[i][0]});
				rg[g[i][0]].pb(i);
			}
		}
		else assert(sz(g[i])==1);
	}
	memres(vis);
	F(n){
		if(vis[i])continue;
		if(sz(g[i])==1){
			Answer(i+1,g[i][0]+1);
			vis[i]=1;
			vis[g[i][0]]=1;
			continue;
		}
		if(g[i][0]!=rg[i][0]&&g[i][0]!=rg[i][1]){
			Answer(i+1,g[i][0]+1);
			vis[i]=1;
			vis[g[i][0]]=1;
		}
		else if(g[i][1]!=rg[i][0]&&g[i][1]!=rg[i][1]){
			Answer(i+1,g[i][1]+1);
			vis[i]=1;
			vis[g[i][1]]=1;
		}
		else{
			Answer(i+1,g[i][2]+1);
			vis[i]=1;
			vis[g[i][2]]=1;
		}
	}
}

#ifdef LOCAL 
signed main(){
	IOS();
	Solve(10);
	return 0;
}
#endif

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