This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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);
}
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: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:44: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:51: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:54:5: note: in expansion of macro 'REP'
REP(k,0,g[v].size()){
^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |