Hugging Face's logo

JustinTX
/
shinka-backup

Model card Files
xet
 Community
shinka-backup / docker_space /frontier_cs_2 /logs /gen_1.cpp
JustinTX's picture
JustinTX
Add files using upload-large-folder tool
14c9c2b verified
Raw History Blame Contribute Delete
5.5 kB
#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();
}