#include "chameleon.h"
#include<bits/stdc++.h>
namespace {
using namespace std;
#define all(x) x.begin(),x.end()
map<vector<int>,int> mp;
int n;
vector<int> cnt;
vector<bool> visited;
mt19937 rng(time(NULL));
int query(vector<int> vec){
sort(vec.begin(),vec.end());
if(mp.find(vec)!=mp.end()) return mp[vec];
else{
/*for(auto v:vec){
cout<<v+1<<' ';
}
cout<<'\n';*/
int x=Query(vec);
mp[vec]=x;
return x;
}
}
void sir(vector<int> vec){
sort(all(vec));
if(mp.find(vec)==mp.end()){
mp[vec]=-1;
}
}
bool comp(int a,int b){
return cnt[a]>cnt[b];
}
} // namespace
void Solve(int N) {
using namespace std;
n=N;
n*=2;
/*vector<int> res(1<<n);
for(int i=0;i<(1<<n);i++){
vector<int> vec;
for(int j=0;j<n;j++){
if(i&(1<<j)){
vec.push_back(j+1);
}
}
res[i]=Query(vec);
}*/
vector<vector<int>> one(n);
vector<bool> two(n);
visited.resize(n);
cnt.resize(n);
for(int i=0;i<n;i++){
vector<int> p(n);
for(int j=0;j<n;j++){
p[j]=j;
}
sort(all(p),comp);
for(int k=0;k<n;k++){
int j=p[k];
if(j==i or j/(n/2)==i/(n/2)) continue;
if(query({i+1,j+1})==1) one[i].push_back(j);
if((int)one[i].size()==3) break;
}
for(int j=0;j<n;j++){
if(j==i) continue;
sir({i,j});
if(query({i,j})!=1) cnt[j]++;
}
if((int)one[i].size()==1){
two[i]=true;
visited[one[i][0]]=true;
}
else{
int a=one[i][0];
int b=one[i][1];
int c=one[i][2];
if(query({i+1,a+1,b+1})==1){
one[i]={a,b};
sir({i+1,b+1,c+1});
sir({i+1,c+1,a+1});
}
else if(query({i+1,b+1,c+1})==1){
one[i]={b,c};
sir({i+1,a+1,b+1});
sir({i+1,c+1,a+1});
}
else if(query({i+1,c+1,a+1})==1){
one[i]={c,a};
sir({i+1,a+1,b+1});
sir({i+1,b+1,c+1});
}
}
}
vector<bool> used(n);
for(int i=0;i<n;i++){
if(used[i]) continue;
if(two[i]){
Answer(i+1,one[i][0]+1);
used[i]=used[one[i][0]]=true;
continue;
}
int a=one[i][0];
int b=one[i][1];
if(two[a]){
Answer(i+1,a+1);
used[i]=used[a]=true;
continue;
}
else if(two[b]){
Answer(i+1,b+1);
used[i]=used[b]=true;
continue;
}
else{
if(one[a][0]==i or one[a][1]==i){
Answer(i+1,a+1);
used[i]=used[a]=true;
}
else{
Answer(i+1,b+1);
used[i]=used[b]=true;
}
}
}
/*return ;
for(int i=0;i<(1<<n);i++){
vector<int> same(n);
vector<int> prv(n,-1);
for(int j=0;j<n;j++){
if(two[j]) continue;
if(i&(1<<j)){
same[j]=1;
prv[one[j][0]]=j;
}
else{
same[j]=0;
prv[one[j][1]]=j;
}
}
bool tf=true;
for(int j=0;j<n;j++){
if(two[j]) continue;
int x=prv[j];
if(x==-1){
tf=false;
break;
}
int y=one[j][same[j]];
if(y==-1){
tf=false;
break;
}
int ans=res[(1<<x)|(1<<j)|(1<<y)];
if(ans!=1){
tf=false;
break;
}
}
if(tf){
vector<bool> used(n);
for(int j=0;j<n;j++){
if(used[j]) continue;
int x=one[j][same[j]];
assert(!used[x]);
Answer(j+1,x+1);
used[j]=used[x]=true;
}
}
}*/
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Runtime error |
6 ms |
2016 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
344 KB |
Wrong Answer [2] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
344 KB |
Wrong Answer [2] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
432 KB |
Output is correct |
| 3 |
Incorrect |
42 ms |
5636 KB |
Wrong Answer [3] |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Runtime error |
6 ms |
2016 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
