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<bits/stdc++.h>
#include "chameleon.h"
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,bo[1009],lef,rig,mid,in[1009],out[1009],col[1009],FX[1009],cnt;
vector <int> v,vv,D[1009],F,S;
int determine(vector <int> q){
vector <int> v;
int A[5];
v.clear();
v.push_back(q[0]);v.push_back(q[1]);v.push_back(q[2]);
A[1]=Query(v);
v.clear();
v.push_back(q[0]);v.push_back(q[1]);v.push_back(q[3]);
A[2]=Query(v);
v.clear();
v.push_back(q[0]);v.push_back(q[2]);v.push_back(q[3]);
A[3]=Query(v);
if(A[1]==A[2]) return q[1];
if(A[1]==A[3]) return q[2];
if(A[2]==A[3]) return q[3];
}
void dfs(int q){
FX[q]=cnt;
col[q]=3-col[q];
for(vector <int>::iterator it=D[q].begin(); it!=D[q].end(); it++){
if(FX[(*it)]==cnt) continue;
dfs((*it));
}
}
void mrg(int q, int w){
if(col[q]!=col[w]) return;
cnt++;
dfs(w);
}
void DO(vector <int> v){
if(v.size()==0) return;
int j,ind=v.size();
for(int TA=1; TA<=3; TA++){
lef=-1;rig=ind;
if(rig<=0) break;
vv.clear();
for(j=0; j<ind; j++){
vv.push_back(v[j]);
}
vv.push_back(i);
c=Query(vv);
if(c==vv.size()) break;
lef=0;
while(1){
if(lef+1>=rig) break;
mid=(lef+rig)/2;
vv.clear();
for(j=mid; j<ind; j++){
vv.push_back(v[j]);
}
vv.push_back(i);
c=Query(vv);
if(c==vv.size()){
rig=mid;
}else{
lef=mid;
}
}
mrg(v[lef],i);
D[v[lef]].push_back(i);
D[i].push_back(v[lef]);
ind=lef;
}
}
void Solve(int NN) {
a=NN;
for(i=0; i<=2*a+1; i++){
bo[i]=0;
}
for(i=1; i<=a*2; i++){
D[i].push_back(i);col[i]=1;
}
for(i=2; i<=a*2; i++){
F.clear();S.clear();
for(j=1; j<i; j++){
if(col[j]==1){
F.push_back(j);
}else{
S.push_back(j);//col[j]==2
}
}
DO(F);
if(D[i].size()==4) continue;
DO(S);
}
//
//
for(i=1; i<=a*2; i++){
if(D[i].size()>2){
c=determine(D[i]);//romelic shedis i-shi
in[i]=c;
out[c]=i;
}
}
for(i=1; i<=a*2; i++){
if(bo[i]!=0) continue;
jj=0;
for(ii=1; ii<D[i].size(); ii++){
j=D[i][ii];
if(bo[j]!=0) continue;
if(i==j) continue;
if(j==in[i]||j==out[i]) continue;
jj=j;break;
}
Answer(i,jj);
bo[i]=1;bo[jj]=1;
}
}
Compilation message (stderr)
chameleon.cpp: In function 'void DO(std::vector<int>)':
chameleon.cpp:47:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | if(c==vv.size()) break;
| ~^~~~~~~~~~~
chameleon.cpp:58:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | if(c==vv.size()){
| ~^~~~~~~~~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:104:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for(ii=1; ii<D[i].size(); ii++){
| ~~^~~~~~~~~~~~
chameleon.cpp: In function 'int determine(std::vector<int>)':
chameleon.cpp:7:18: warning: control reaches end of non-void function [-Wreturn-type]
7 | vector <int> v;
| ^
# | 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... |