/* 想定解より削れるので一応解説 Q=550の方針、つまり分割統治までは同じで、片方の桁は大体260回ぐらいで終わるとします 問題はQ=450のところで、18回期待値で10個確定できるのって結構非自明じゃないですか? だってlog_2(10!)って22ぐらいじゃないですか ということを唸っていたら、以下の方針を思いつきました。 やりたいことは想定解とほとんど同じで、10個のブロックを1つ1つ確定させていきます。 ただし上述の理由で少し心もとないので、暗号の結果を2桁一致まで教えてくれることを利用して2倍の短縮をします。 片方のブロックについては1つの桁のみを使ってクエリを投げて(使わない桁は?を埋める)、 もう片方のブロックについてはすでに分かっている桁も合わせて2桁でクエリを投げます。 すると、後者については2桁一致が見つかればそれがそのまま見つかった数に一致して、 前者についてはそれも踏まえた上で1桁一致の数を数えれば結果を知ることが出来ます。 よってかなりクエリ回数に余裕が出てきます。 2桁まで教えてくれるって言うから絶対これが想定解だな〜〜〜賢いなぁ〜〜〜 とか思ってたら期待値ゲーが想定だったというオチ(なんだそのオチ) */ #include using namespace std; #define REP(i,n) for(int i=0;i<(int)(n);i++) #define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define FORR(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--) typedef long long ll; typedef vector vi; int perm[125]; int revperm[125]; char s[353]; int p0, p1, p2; void clear(){ REP(i,100){ s[3*i] = s[3*i+1] = '?'; s[3*i+2] = ' '; } s[299] = '\0'; } void setval(int p, int u, int d){ p = perm[p]; s[3*p+0] = u==-1 ? '?' : '0'+u; s[3*p+1] = d==-1 ? '?' : '0'+d; } void query(){ puts(s);fflush(stdout); scanf("%d%d%d",&p0,&p1,&p2); } int u[125]; int d[125]; void solve_d(vi cand, int rest, int val){ if(cand.size() == rest){ // all ok REP(i,cand.size()){ d[cand[i]] = val; } return; } if(rest == 0){ return; } // split into 2 segment int m = cand.size() / 2; clear(); REP(i,m)setval(cand[i], -1, val); query(); vi va, vb; REP(i,m)va.push_back(cand[i]); FOR(i,m,cand.size())vb.push_back(cand[i]); int x = p1; int y = rest-p1; solve_d(va, x, val); solve_d(vb, y, val); } void dfs_u(vi ca, vi cb, vi va, vi vb){ if(ca.size() == 1){ u[ca[0]] = va[0]; u[cb[0]] = vb[0]; return; } int n = ca.size(); vi lca, rca, lcb, rcb, lva, rva, lvb, rvb; REP(i,n/2){ lca.push_back(ca[i]); lcb.push_back(cb[i]); } FOR(i,n/2,n){ rca.push_back(ca[i]); rcb.push_back(cb[i]); } REP(i,n-1){ int a = va[i]; int b = vb[i]; clear(); REP(j,lca.size()){ setval(lca[j], a, -1); setval(lcb[j], b, d[lcb[j]]); } query(); int x = p1, y = p2; if(y==1){ // b in left lvb.push_back(b); x++; }else{ rvb.push_back(b); } if(x==lca.size()+1){ // a in left lva.push_back(a); }else{ rva.push_back(a); } } (lva.size()==lca.size() ? rva : lva).push_back(va.back()); (lvb.size()==lcb.size() ? rvb : lvb).push_back(vb.back()); dfs_u(lca, lcb, lva, lvb); dfs_u(rca, rcb, rva, rvb); } void solve_u(int a, int b){ vi ca, cb; REP(i,100){ if(d[i]==a)ca.push_back(i); if(d[i]==b)cb.push_back(i); } vi va, vb; REP(i,10)va.push_back(i); REP(i,10)vb.push_back(i); dfs_u(ca, cb, va, vb); } int main(){ int q;cin>>q; REP(i,100)u[i] = d[i] = -1; // randomize srand(time(NULL)); REP(i,100)perm[i] = i; random_shuffle(perm, perm+100); REP(i,100)revperm[perm[i]] = i; // solve for d REP(i,10){ vi cand; REP(j,100)if(d[j]==-1)cand.push_back(j); solve_d(cand, 10, i); } // solve for u REP(i,5){ solve_u(2*i, 2*i+1); } // ok REP(i,100)printf("%d%d%c",u[revperm[i]],d[revperm[i]],i==99?'\n':' '); fflush(stdout); scanf("%d%d%d",&p0,&p1,&p2); return 0; }