#include #include #include #include #include #include #include #include using namespace std; int a[100]; vector ans; int query_count = 0; #ifdef LOCAL array ask(vector q) { array res = {}; for (int i = 0; i < 100; i++) { int hit = 0; hit += q[i][0] - '0' == a[i] / 10; hit += q[i][1] - '0' == a[i] % 10; res[hit]++; } query_count++; return res; } #else array ask(vector q) { for (int i = 0; i < q.size(); i++) { if (i != 0) cout << ' '; cout << q[i]; } cout << endl; array res; for (int i = 0; i < 3; i++) { cin >> res[i]; } if (res[2] == 100) { exit(0); } return res; } #endif int ask_uniform(int val, const vector &pos, int l, int r, bool low) { vector query(100, "??"); for (int i = l; i < r; i++) { query[pos[i]][low] = val + '0'; } return ask(query)[1]; } pair ask_uniform2(int v, const vector &pos, int l0, int r0, int l1, int r1) { vector query(100, "??"); for (int i = l0; i < r0; i++) { query[pos[i]][0] = ans[pos[i]][0] == '9' ? '0' : ans[pos[i]][0] + 1; query[pos[i]][1] = v + '0'; } for (int i = l1; i < r1; i++) { query[pos[i]][0] = ans[pos[i]][0]; query[pos[i]][1] = v + '0'; } auto res = ask(query); return {res[1] - (r1 - l1 - res[2]), res[2]}; } void rec(const vector &pos, int l, int r, int v, int c, bool low) { queue> q; if (c == 0) return; if (r - l == c) { for (int i = l; i < r; i++) { ans[pos[i]][low] = v + '0'; } return; } int m = (l + r) / 2; int c0 = ask_uniform(v, pos, l, m, low); int c1 = c - c0; rec(pos, l, m, v, c0, low); rec(pos, m, r, v, c1, low); } int main() { ans.resize(100, "??"); #ifdef LOCAL mt19937 mt(17); for (int i = 0; i < 100; i++) { a[i] = i; } shuffle(a, a + 100, mt); #else int q; cin >> q; #endif for (int i = 0; i < 10; i++) { vector pos; for (int k = 0; k < 100; k++) { if (ans[k][0] == '?') { pos.push_back(k); } } rec(pos, 0, pos.size(), i, 10, false); } #ifdef LOCAL for (int i = 0; i < 100; i++) { printf("%02d %s\n", a[i], ans[i].c_str()); } cout << "query count" << query_count << endl; #endif for (int v = 0; v < 10; v++) { vector pos; for (int k = 0; k < 100; k++) { if (ans[k][1] == '?') { pos.push_back(k); } } queue> q; q.emplace(0, pos.size(), 10); while (!q.empty()) { int l, r, c; tie(l, r, c) = q.front(); q.pop(); if (r - l == c) { for (int i = l; i < r; i++) { ans[pos[i]][1] = v + '0'; } continue; } int m = (l + r) / 2; int ll = -1, rr, cc; while (!q.empty()) { int l1, r1, c1; tie(l1, r1, c1) = q.front(); q.pop(); if (r1 - l1 == c1) { for (int i = l1; i < r1; i++) { ans[pos[i]][1] = v + '0'; } continue; } ll = l1; rr = r1; cc = c1; break; } if (ll == -1) { int c0 = ask_uniform(v, pos, l, m, true); int c1 = c - c0; if (c0 > 0) q.emplace(l, m, c0); if (c1 > 0) q.emplace(m, r, c1); } else { int mm = (ll + rr) / 2; int c0, cc0; tie(c0, cc0) = ask_uniform2(v, pos, l, m, ll, mm); int c1 = c - c0; int cc1 = cc - cc0; if (c0 > 0) q.emplace(l, m, c0); if (c1 > 0) q.emplace(m, r, c1); if (cc0 > 0) q.emplace(ll, mm, cc0); if (cc1 > 0) q.emplace(mm, rr, cc1); } } } #ifdef LOCAL for (int i = 0; i < 100; i++) { printf("%02d %s\n", a[i], ans[i].c_str()); } cout << "query count" << query_count << endl; #else ask(ans); #endif }