#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());
}
}
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);
}
REP(i,0,m){
REP(j,0,i){
int x=Query({i+1,j+1});
if(x==1)g[i].pb(j),g[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
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:40: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:50: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:57: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:60:5: note: in expansion of macro 'REP'
REP(k,0,g[v].size()){
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Wrong Answer [4] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Wrong Answer [4] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Wrong Answer [4] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Wrong Answer [4] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Wrong Answer [4] |
| 2 |
Halted |
0 ms |
0 KB |
- |
