結果
問題 | No.2848 Birthday Hit and Blow |
ユーザー | Kude |
提出日時 | 2024-08-23 22:53:35 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 157 ms / 2,000 ms |
コード長 | 2,888 bytes |
コンパイル時間 | 3,044 ms |
コンパイル使用メモリ | 278,552 KB |
実行使用メモリ | 24,836 KB |
平均クエリ数 | 445.50 |
最終ジャッジ日時 | 2024-08-23 22:53:39 |
合計ジャッジ時間 | 3,851 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 26 ms
24,812 KB |
testcase_01 | AC | 157 ms
24,836 KB |
ソースコード
#include<bits/stdc++.h> namespace { #pragma GCC diagnostic ignored "-Wunused-function" #include<atcoder/all> #pragma GCC diagnostic warning "-Wunused-function" using namespace std; using namespace atcoder; #define rep(i,n) for(int i = 0; i < (int)(n); i++) #define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--) #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; } template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; } using ll = long long; using P = pair<int,int>; using VI = vector<int>; using VVI = vector<VI>; using VL = vector<ll>; using VVL = vector<VL>; P get_xy(array<int, 4> d, array<int, 4> c) { int x = 0; rep(i, 4) x += c[i] == d[i]; int bd = 0, bc = 0; for (int di : d) bd |= 1 << di; for (int ci : c) bc |= 1 << ci; int y = popcount(0U + (bc & bd)) - x; return {x, y}; } constexpr int D[]{0, 31,29,31,30,31,30,31,31,30,31,30,31}; vector<array<int, 4>> days; array<int, 4> test; array<int, 4> get_next(vector<array<int, 4>> &cands) { int fmx = 1001001001; array<int, 4> res{}; for (auto d : days) { int f[5][5]{}; int bd = 0; for (int di : d) bd |= 1 << di; for (auto c : cands) { auto [x, y] = get_xy(d, c); f[x][y]++; } int t = 0; rep(i, 5) rep(j, 5) chmax(t, f[i][j]); if (chmin(fmx, t)) res = d; } return res; } } int main() { ios::sync_with_stdio(false); cin.tie(0); int cnt = 0; for (int m = 1; m <= 12; m++) { for (int d = 1; d <= D[m]; d++) { int seen = 0; seen |= 1 << m / 10 | 1 << m % 10 | 1 << d / 10 | 1 << d % 10; if (popcount(0U + seen) != 4) continue; days.push_back({m / 10, m % 10, d / 10, d % 10}); cnt++; } } // int mx_cnt = 0; // for (auto d : days) { // test = d; // int cnt = 0; // auto cands = days; // while (cands.size() > 1) { // cnt++; // auto d = get_next(cands); // auto xy = get_xy(test, d); // vector<array<int, 4>> nc; // for (auto c : cands) if (get_xy(c, d) == xy) { // nc.emplace_back(c); // } // swap(cands, nc); // } // chmax(mx_cnt, cnt); // } // cout << mx_cnt << endl; int tt; cin >> tt; auto ask = [](array<int, 4> d) { cout << "? " << d[0] << d[1] << d[2] << d[3] << endl; int x, y; cin >> x >> y; return pair(x, y); }; while (tt--) { auto cands = days; while (cands.size() > 1) { auto d = get_next(cands); auto xy = ask(d); vector<array<int, 4>> nc; for (auto c : cands) if (get_xy(c, d) == xy) { nc.emplace_back(c); } swap(cands, nc); } auto c = cands[0]; cout << "! " << c[0] << c[1] << c[2] << c[3] << endl; int res; cin >> res; assert(res == 0); } }