#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;
int query(vector<int> vec){
sort(vec.begin(),vec.end());
if(mp.find(vec)!=mp.end()) return mp[vec];
else{
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;
}
}
} // 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);
for(int i=0;i<n;i++){
vector<int> p(n);
for(int j=0;j<n;j++){
p[j]=j;
}
mt19937 rng(time(NULL));
shuffle(all(p),rng);
for(int k=n-1;k>=0;k--){
int j=p[k];
if(j==i) 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((int)one[i].size()==1) two[i]=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;
}
}
}*/
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Incorrect |
24 ms |
2648 KB |
Wrong Answer [3] |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
460 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
460 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
5 ms |
856 KB |
Output is correct |
11 |
Correct |
5 ms |
856 KB |
Output is correct |
12 |
Correct |
5 ms |
928 KB |
Output is correct |
13 |
Correct |
5 ms |
856 KB |
Output is correct |
14 |
Correct |
5 ms |
856 KB |
Output is correct |
15 |
Correct |
5 ms |
856 KB |
Output is correct |
16 |
Correct |
5 ms |
856 KB |
Output is correct |
17 |
Correct |
5 ms |
856 KB |
Output is correct |
18 |
Correct |
5 ms |
856 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Incorrect |
27 ms |
3672 KB |
Wrong Answer [3] |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Incorrect |
24 ms |
2648 KB |
Wrong Answer [3] |
4 |
Halted |
0 ms |
0 KB |
- |