#include using namespace std; // ===================== // Code representation // ===================== struct Code { array d; // digits uint16_t mask; // 10-bit mask string s; // "01234" }; static int OFF[6]; // offset for type index static const int TYPE20 = 20; // (5,0) static const int N = 30240; // 10P5 // type index from (hits, blows) inline int hb_to_type(int h, int b) { return OFF[h] + b; } // ===================== // Query info // ===================== struct QueryInfo { int qidx; // index in codes[] vector types; // types[i] = type(secret=codes[i], query=this->qidx) array rem; // remaining unknown secrets count per type for THIS query }; // popcount for uint16_t inline int popc16(uint16_t x) { return __builtin_popcount((unsigned)x); } // Compute type(secretIdx, queryIdx) inline uint8_t calc_type(const vector& codes, int secretIdx, int queryIdx) { const auto& a = codes[secretIdx]; const auto& q = codes[queryIdx]; int hit = 0; for (int i = 0; i < 5; i++) hit += (a.d[i] == q.d[i]); int common = popc16(a.mask & q.mask); int blow = common - hit; return (uint8_t)hb_to_type(hit, blow); } // Choose IPF iterations based on time/candidate size (runtime tuning) int choose_ipf_iters(double elapsed_sec, int cand_size) { // Safe-ish tuning: more iterations early, fewer late. if (elapsed_sec > 4.3) return 2; if (elapsed_sec > 3.5) return 3; if (cand_size > 20000) return 3; return 5; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // Build OFF[] OFF[0] = 0; for (int h = 0; h < 5; h++) OFF[h + 1] = OFF[h] + (6 - h); // Generate all 10P5 codes vector codes; codes.reserve(N); unordered_map idx_of; idx_of.reserve(N * 2); for (int a = 0; a <= 9; a++) for (int b = 0; b <= 9; b++) if (b != a) for (int c = 0; c <= 9; c++) if (c != a && c != b) for (int d = 0; d <= 9; d++) if (d != a && d != b && d != c) for (int e = 0; e <= 9; e++) if (e != a && e != b && e != c && e != d) { Code x; x.d = {(uint8_t)a,(uint8_t)b,(uint8_t)c,(uint8_t)d,(uint8_t)e}; x.mask = (uint16_t)((1u< state(N, 0); vector queries; queries.reserve(80); int foundCount = 0; auto t0 = chrono::steady_clock::now(); while (true) { // Ask cout << codes[qidx].s << "\n"; cout.flush(); // Read response: 30 lines of (Hi, Bi) array raw{}; raw.fill(0); for (int i = 0; i < 30; i++) { int h, b; if (!(cin >> h >> b)) return 0; // EOF safeguard if (h == -1 && b == -1) return 0; // judge error // type index int t = hb_to_type(h, b); raw[t]++; } int beforeFound = foundCount; int afterFound = raw[TYPE20]; bool hit = (afterFound > beforeFound); // Build query info: types for all codes QueryInfo qi; qi.qidx = qidx; qi.types.resize(N); for (int i = 0; i < N; i++) { qi.types[i] = calc_type(codes, i, qidx); } // Initialize remaining counts for "unknown secrets now" qi.rem = raw; // subtract secrets that were already found BEFORE this query qi.rem[TYPE20] -= beforeFound; queries.push_back(std::move(qi)); int k = (int)queries.size() - 1; if (hit) { // qidx itself is a new secret state[qidx] = 2; foundCount++; // Retroactively subtract this secret from all previous queries: // for queries < k: it contributed its actual type for (int j = 0; j < k; j++) { uint8_t t = queries[j].types[qidx]; queries[j].rem[t]--; } // for query k: it contributed (5,0) queries[k].rem[TYPE20]--; } else { state[qidx] = 1; } if (foundCount >= 30) break; // Recompute candidate list (only eliminate by 0-bins + already-asked) vector cand; cand.reserve(N); for (int i = 0; i < N; i++) { if (state[i] != 0) continue; bool ok = true; for (const auto& qq : queries) { uint8_t t = qq.types[i]; if (qq.rem[t] == 0) { ok = false; break; } } if (ok) cand.push_back(i); } if (cand.empty()) { // Should not happen if everything is consistent, but just in case: for (int i = 0; i < N; i++) if (state[i] == 0) { qidx = i; break; } continue; } // IPF to estimate max-entropy distribution p over candidates int C = (int)cand.size(); vector p(C, 1.0 / (double)C); int remaining = 30 - foundCount; auto now = chrono::steady_clock::now(); double elapsed = chrono::duration(now - t0).count(); int iters = choose_ipf_iters(elapsed, C); for (int it = 0; it < iters; it++) { for (const auto& qq : queries) { double curr[21]; for (int t = 0; t < 21; t++) curr[t] = 0.0; for (int i = 0; i < C; i++) { uint8_t t = qq.types[cand[i]]; curr[t] += p[i]; } double factor[21]; for (int t = 0; t < 21; t++) { if (qq.rem[t] <= 0) { factor[t] = 0.0; // candidates should not be in this bin anyway } else { double target = (double)qq.rem[t] / (double)remaining; double denom = curr[t]; if (denom <= 0.0) { // In a consistent state, this shouldn't happen. // Keep it neutral to avoid NaN explosion. factor[t] = 1.0; } else { factor[t] = target / denom; } } } double sumP = 0.0; for (int i = 0; i < C; i++) { uint8_t t = qq.types[cand[i]]; p[i] *= factor[t]; sumP += p[i]; } if (!(sumP > 0.0) || !isfinite(sumP)) { // reset if numerically broken double uni = 1.0 / (double)C; for (int i = 0; i < C; i++) p[i] = uni; } else { double inv = 1.0 / sumP; for (int i = 0; i < C; i++) p[i] *= inv; } } } // Choose argmax int bestPos = 0; for (int i = 1; i < C; i++) { if (p[i] > p[bestPos]) bestPos = i; } qidx = cand[bestPos]; } return 0; }