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],eds[maxm][maxm];
m=n<<1;
REP(i,0,n){
int l=n,r=m;
while(1){
if(!ch::check(i,l,r))break;
while(l+1<r){
int mid=l+r>>1;
if(ch::check(i,l,mid))r=mid;
else l=mid;
}
g[i].pb(l);
g[l].pb(i);
eds[i][l]=eds[l][i]=1;
l=r,r=m;
}
}
REP(u,0,m){
if(g[u].size()<2)continue;
REP(i,1,g[u].size()){
int v=g[u][i];
vector<int>tt;
tt.pb(u+1);
REP(j,0,g[u].size()){
if(j!=i){
tt.pb(g[u][j]+1);
}
}
if(Query(tt)==1){
eds[u][v]=eds[v][u]=0;
goto fin;
}
}
eds[u][g[u][0]]=eds[g[u][0]][u]=0;
fin:;
}
REP(i,0,n){
REP(j,0,g[i].size()){
int v=g[i][j];
if(eds[i][v]){
mch[i]=v;
}
}
}
REP(i,0,n)Answer(i+1,mch[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:43:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=l+r>>1;
~^~
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:55:3: note: in expansion of macro 'REP'
REP(i,1,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:59: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:73:3: note: in expansion of macro 'REP'
REP(j,0,g[i].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... |