Submission #212843

#	Time	Username	Problem	Language	Result	Execution time	Memory
212843		username	Chameleon's Love (JOI20_chameleon)	C++14	0 / 100	52 ms	464 KiB

chameleon

#include "chameleon.h"
//
#include<bits/stdc++.h>
#define REP(i,j,k) for(int i=(j);i<(k);++i)
#define pb push_back
using namespace std;

namespace ch{
	bool check(int x,int l,int r){
		vector<int>tt;
		tt.pb(x+1);
		REP(i,l,r)tt.pb(i+1);
		return Query(tt)<r-l+1;
	}
	vector<int>dfs(int x,int l,int r){
		vector<int>re,tt;
		if(l+1==r)re.pb(l);
		else{
			int mid=l+r>>1;
			if(check(x,l,mid)){
				tt=dfs(x,l,mid);
				re.insert(re.end(),tt.begin(),tt.end());
				if(check(x,mid,r)){
					tt=dfs(x,mid,r);
					re.insert(re.end(),tt.begin(),tt.end());
				}
			}else{
				tt=dfs(x,mid,r);
				re.insert(re.end(),tt.begin(),tt.end());
			}
		}
		return re;
	}
}

void Solve(int n){
	const int maxm=1009;
	vector<int>g[maxm];
	int m,mch[maxm];
	m=n<<1;
	REP(i,0,n){
		vector<int>tt=ch::dfs(i,n,m);
		REP(j,0,tt.size())g[i].pb(tt[j]),g[tt[j]].pb(i);
	}
	memset(mch,-1,sizeof mch);
	REP(u,0,m){
		REP(i,0,g[u].size()){
			int v=g[u][i];
			if(mch[u]>=0||mch[v]>=0)continue;
			if(g[u].size()==1||g[v].size()==1){
				mch[u]=v,mch[v]=u;
				continue;
			}
			REP(j,0,g[u].size()){
				int nv=g[u][j];
				if(nv==v)continue;				
				REP(k,0,g[v].size()){
					int nu=g[v][k];
					if(nu==u)continue;
					if(Query({u+1,v+1,nv+1})==1&&Query({u+1,nu+1,v+1})==1){
						mch[u]=v,mch[v]=u;
						goto fin;
					}
				}
			}
			fin:;
		}
	}
	REP(i,0,m)if(mch[i]<i)Answer(mch[i]+1,i+1);
}
//

Compilation message (stderr)

chameleon.cpp: In function 'std::vector<int> ch::dfs(int, int, int)':
chameleon.cpp:19:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid=l+r>>1;
            ~^~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:4:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(int i=(j);i<(k);++i)
                                   ^
chameleon.cpp:43:3: note: in expansion of macro 'REP'
   REP(j,0,tt.size())g[i].pb(tt[j]),g[tt[j]].pb(i);
   ^~~
chameleon.cpp:4:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(int i=(j);i<(k);++i)
                                   ^
chameleon.cpp:47:3: note: in expansion of macro 'REP'
   REP(i,0,g[u].size()){
   ^~~
chameleon.cpp:4:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(int i=(j);i<(k);++i)
                                   ^
chameleon.cpp:54:4: note: in expansion of macro 'REP'
    REP(j,0,g[u].size()){
    ^~~
chameleon.cpp:4:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(int i=(j);i<(k);++i)
                                   ^
chameleon.cpp:57:5: note: in expansion of macro 'REP'
     REP(k,0,g[v].size()){
     ^~~

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