File size: 5,496 Bytes
14c9c2b | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 | #include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
static char obuf[1<<22]; static int opos;
void oflush(){fwrite(obuf,1,opos,stdout);opos=0;fflush(stdout);}
void ochar(char c){obuf[opos++]=c;}
void oint(int x){
if(x>=1000){ochar('0'+x/1000);ochar('0'+(x/100)%10);ochar('0'+(x/10)%10);ochar('0'+x%10);}
else if(x>=100){ochar('0'+x/100);ochar('0'+(x/10)%10);ochar('0'+x%10);}
else if(x>=10){ochar('0'+x/10);ochar('0'+x%10);}
else ochar('0'+x);
}
int N,q[1001],perm[1001];
int kc; // known count (positions where perm[] is set and q[] matches)
int ask(){ochar('0');for(int i=0;i<N;i++){ochar(' ');oint(q[i]);}ochar('\n');oflush();int x;scanf("%d",&x);return x;}
void submit(){ochar('1');for(int i=0;i<N;i++){ochar(' ');oint(perm[i]);}ochar('\n');oflush();exit(0);}
// Divide and conquer: given a set of values and a set of positions,
// determine which value goes to which position.
// vals: values to place
// pos: positions (indices into the global position space)
// All non-pos positions in q[] are set to 1 (background, safe since pos1 is known)
void solve(vector<int>& vals, vector<int>& pos) {
int n = vals.size();
if (n == 0) return;
if (n == 1) {
// Single value, single position
perm[pos[0]] = vals[0];
q[pos[0]] = vals[0];
kc++;
return;
}
if (n == 2) {
// 2 values, 2 positions. 1 query.
q[pos[0]] = vals[0];
int r = ask();
q[pos[0]] = 1;
if (r == kc + 1) {
perm[pos[0]] = vals[0]; q[pos[0]] = vals[0];
perm[pos[1]] = vals[1]; q[pos[1]] = vals[1];
} else {
perm[pos[0]] = vals[1]; q[pos[0]] = vals[1];
perm[pos[1]] = vals[0]; q[pos[1]] = vals[0];
}
kc += 2;
return;
}
// Split positions into left and right halves
int half = n / 2;
// left positions: pos[0..half-1], right positions: pos[half..n-1]
// For each value, determine if it's in the left or right half.
// Process values in pairs.
vector<int> left_vals, right_vals;
int vi = 0;
while (vi < n) {
if (vi + 1 >= n) {
// Odd value out. Query to determine its half.
int v = vals[vi];
// Set left positions to v, rest to 1
for (int i = 0; i < half; i++) q[pos[i]] = v;
int r = ask();
for (int i = 0; i < half; i++) q[pos[i]] = 1;
if (r == kc + 1) left_vals.push_back(v);
else right_vals.push_back(v);
vi++;
continue;
}
int v = vals[vi], w = vals[vi + 1];
// Paired query: left=v, right=w
for (int i = 0; i < half; i++) q[pos[i]] = v;
for (int i = half; i < n; i++) q[pos[i]] = w;
int r = ask();
for (int i = 0; i < half; i++) q[pos[i]] = 1;
for (int i = half; i < n; i++) q[pos[i]] = 1;
if (r == kc + 2) {
// v in left, w in right
left_vals.push_back(v);
right_vals.push_back(w);
} else if (r == kc) {
// v in right, w in left
right_vals.push_back(v);
left_vals.push_back(w);
} else {
// Same half. Disambiguate: query left=v only
for (int i = 0; i < half; i++) q[pos[i]] = v;
int r2 = ask();
for (int i = 0; i < half; i++) q[pos[i]] = 1;
if (r2 == kc + 1) {
// Both in left
left_vals.push_back(v);
left_vals.push_back(w);
} else {
// Both in right
right_vals.push_back(v);
right_vals.push_back(w);
}
}
vi += 2;
}
// Recurse on left and right
vector<int> left_pos(pos.begin(), pos.begin() + half);
vector<int> right_pos(pos.begin() + half, pos.end());
solve(left_vals, left_pos);
solve(right_vals, right_pos);
}
int main(){
scanf("%d",&N);
memset(perm,0,sizeof(perm));
if(N==1){perm[0]=1;submit();}
if(N==2){q[0]=1;q[1]=2;if(ask()==2){perm[0]=1;perm[1]=2;}else{perm[0]=2;perm[1]=1;}submit();}
// Phase 1: Find pos1 and pos3 using bit queries
int B=0;{int tmp=N-1;while(tmp>0){B++;tmp>>=1;}}
int rb[12];
for(int b=0;b<B;b++){
for(int i=0;i<N;i++) q[i]=(i&(1<<b))?1:3;
rb[b]=ask();
}
int kb1=0,kb3=0,kmask=0;
for(int b=0;b<B;b++){
if(rb[b]==0){kmask|=(1<<b);kb3|=(1<<b);}
else if(rb[b]==2){kmask|=(1<<b);kb1|=(1<<b);}
}
int amask=((1<<B)-1)&~kmask,P=0;
for(int b=0;b<B;b++){
if(!(amask&(1<<b)))continue;
for(int i=0;i<N;i++){
q[i]=((i&(1<<b))&&(i&kmask)==kb1)?1:3;
}
int r=ask();
if(r==2) P|=(1<<b);
}
int p1=kb1|(P&amask);
int p3=kb3|(P&amask);
if(p1<0||p1>=N||p3<0||p3>=N||p1==p3){
p1=-1;p3=-1;
for(int i=0;i<N;i++){
if(p1>=0&&p3>=0)break;
for(int j=0;j<N;j++)q[j]=3;q[i]=1;
int r=ask();
if(r==2)p1=i;else if(r==0)p3=i;
}
}
perm[p1]=1;perm[p3]=3;
kc=2;
for(int i=0;i<N;i++) q[i]=1;
q[p1]=1;q[p3]=3;
// Collect unknown values and positions
vector<int> vals, pos;
vals.push_back(2);
for(int v=4;v<=N;v++) vals.push_back(v);
for(int i=0;i<N;i++) if(i!=p1&&i!=p3) pos.push_back(i);
// Divide and conquer
solve(vals, pos);
submit();
}
|