#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
void Solve(int n) {
vector<bool> was(n*2+1,false);
vector<vector<int>> cand(n*2+1,vector<int>());
vector<int> take,ost,ids;
for(int i=1;i<=n*2;i++)ids.pb(i);
mt19937 rng(time(0));
do{
take.clear();ost.clear();
shuffle(ids.begin(),ids.end(),rng);
for(int i:ids){
take.pb(i);
if(take.size()>1&&Query(take)!=take.size())take.pop_back(),ost.pb(i);
}
}while(take.size()!=n);
//printf("take size: %i n:%i\n",take.size(),n);
set<pii> bad;
for(int j:ost){
vector<int> all;
all=take;
for(int work=1;work<=3;work++){
if(all.empty())break;
vector<int> tmp=all;
while(tmp.size()>1){
vector<int> v[2];
for(int i=0;i<tmp.size();i++)v[i&1].pb(tmp[i]);
v[0].pb(j);
int B=Query(v[0]);
v[0].pop_back();
if(B<=v[0].size())tmp=v[0];
else tmp=v[1];
}
if(work==2&&Query({j,tmp[0]})==2)break;
cand[j].pb(tmp[0]);
cand[tmp[0]].pb(j);
vector<int> nxt;
for(int i:all)if(i!=tmp[0])nxt.pb(i);
all=nxt;
}
}
for(int j=1;j<=n*2;j++){
assert(cand[j].size()==1||cand[j].size()==3);
if(cand[j].size()==3){
int A=Query({j,cand[j][0],cand[j][1]});
int B=Query({j,cand[j][1],cand[j][2]});
int C=Query({j,cand[j][2],cand[j][0]});
if(A==1)bad.insert({j,cand[j][2]});
if(B==1)bad.insert({j,cand[j][0]});
if(C==1)bad.insert({j,cand[j][1]});
}
}
for(int j=1;j<=n*2;j++){
if(was[j])continue;
for(int i:cand[j]){
if(!bad.count({i,j})&&!bad.count({j,i})){
Answer(i,j);
was[i]=was[j]=true;
break;
}
}
}
/*if(n<=50){
vector<bool> was(n*2+1,false);
vector<vector<int>> cand(n*2+1,vector<int>());
set<pii> bad;
for(int j=1;j<=n*2;j++){
for(int i=1;i<=n*2;i++)if(i!=j){
if(Query({j,i})==1)cand[j].pb(i);
}
assert(cand[j].size()==1||cand[j].size()==3);
if(cand[j].size()==3){
int A=Query({j,cand[j][0],cand[j][1]});
int B=Query({j,cand[j][1],cand[j][2]});
int C=Query({j,cand[j][2],cand[j][0]});
if(A==1)bad.insert({j,cand[j][2]});
if(B==1)bad.insert({j,cand[j][0]});
if(C==1)bad.insert({j,cand[j][1]});
}
}
for(int j=1;j<=n*2;j++){
if(was[j])continue;
for(int i:cand[j]){
if(!bad.count({i,j})&&!bad.count({j,i})){
Answer(i,j);
was[i]=was[j]=true;
break;
}
}
}
}else{
vector<bool> was(n*2+1,false);
vector<vector<int>> cand(n*2+1,vector<int>());
set<pii> bad;
for(int j=1;j<=n*2;j++){
vector<int> all;
if(j<=n){
for(int i=n+1;i<=n*2;i++)all.pb(i);
for(int work=1;work<=3;work++){
vector<int> tmp=all;
while(tmp.size()>1){
vector<int> v[2];
for(int i=0;i<tmp.size();i++)v[i&1].pb(tmp[i]);
v[0].pb(j);
int B=Query(v[0]);
v[0].pop_back();
if(B<=v[0].size())tmp=v[0];
else tmp=v[1];
}
if(work==2&&Query({j,tmp[0]})==2)break;
cand[j].pb(tmp[0]);
cand[tmp[0]].pb(j);
vector<int> nxt;
for(int i:all)if(i!=tmp[0])nxt.pb(i);
all=nxt;
}
}
assert(cand[j].size()==1||cand[j].size()==3);
if(cand[j].size()==3){
int A=Query({j,cand[j][0],cand[j][1]});
int B=Query({j,cand[j][1],cand[j][2]});
int C=Query({j,cand[j][2],cand[j][0]});
if(A==1)bad.insert({j,cand[j][2]});
if(B==1)bad.insert({j,cand[j][0]});
if(C==1)bad.insert({j,cand[j][1]});
}
}
for(int j=1;j<=n*2;j++){
if(was[j])continue;
for(int i:cand[j]){
if(!bad.count({i,j})&&!bad.count({j,i})){
Answer(i,j);
was[i]=was[j]=true;
break;
}
}
}*/
/*vector<bool> was(n*2+1,false);
for(int j=1;j<=n*2;j++){
if(was[j])continue;
vector<int> all;
for(int i=1;i<=n*2;i++)if(i!=j)all.pb(i);
while(all.size()>1){
vector<int> v[2];
for(int i=0;i<all.size();i++)v[i&1].pb(all[i]);
int A=Query(v[0]);
v[0].pb(j);
int B=Query(v[0]);
v[0].pop_back();
if(A==B)all=v[0];
else all=v[1];
}
was[all[0]]=was[j]=true;
Answer(j,all[0]);
}*/
//}
}
Compilation message
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:18:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(take.size()>1&&Query(take)!=take.size())take.pop_back(),ost.pb(i);
~~~~~~~~~~~^~~~~~~~~~~~~
chameleon.cpp:20:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
}while(take.size()!=n);
~~~~~~~~~~~^~~
chameleon.cpp:32:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<tmp.size();i++)v[i&1].pb(tmp[i]);
~^~~~~~~~~~~
chameleon.cpp:36:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(B<=v[0].size())tmp=v[0];
~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
37 ms |
384 KB |
Output is correct |
| 4 |
Correct |
40 ms |
384 KB |
Output is correct |
| 5 |
Correct |
45 ms |
384 KB |
Output is correct |
| 6 |
Correct |
39 ms |
384 KB |
Output is correct |
| 7 |
Correct |
37 ms |
384 KB |
Output is correct |
| 8 |
Correct |
36 ms |
384 KB |
Output is correct |
| 9 |
Correct |
37 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Runtime error |
5 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Runtime error |
5 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
65 ms |
384 KB |
Wrong Answer [3] |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
37 ms |
384 KB |
Output is correct |
| 4 |
Correct |
40 ms |
384 KB |
Output is correct |
| 5 |
Correct |
45 ms |
384 KB |
Output is correct |
| 6 |
Correct |
39 ms |
384 KB |
Output is correct |
| 7 |
Correct |
37 ms |
384 KB |
Output is correct |
| 8 |
Correct |
36 ms |
384 KB |
Output is correct |
| 9 |
Correct |
37 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 ms |
384 KB |
Output is correct |
| 12 |
Runtime error |
5 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Halted |
0 ms |
0 KB |
- |
