結果

問題 No.3120 Lower Nim
ユーザー shibh308
提出日時 2025-04-20 19:30:12
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,154 bytes
コンパイル時間 2,200 ms
コンパイル使用メモリ 195,532 KB
実行使用メモリ 25,972 KB
平均クエリ数 114.23
最終ジャッジ日時 2025-04-20 19:30:20
合計ジャッジ時間 7,203 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other AC * 6 TLE * 1 -- * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;            // 山の数
    cin >> N;
    vector<int> A(N); // 各山
    for (int &v : A) cin >> v;

    auto next_pow2 = [](int64 k) {
        int64 p = 1;
        while (p <= k) p <<= 1;
        return p;          // k をこえる最小の 2 のべき
    };

    auto nim_xor = [&](int64 P)->int64 {
        int64 x = 0;
        for (int v : A) x ^= (v % P);
        return x;
    };

    // ---------- 先攻／後攻を決める ----------
    int64 hugeK = (int64)1e18;           // 10^100 と同じ扱い
    int64 first_xor = nim_xor(next_pow2(hugeK));   // = 通常の xor
    bool iamFirst = (first_xor != 0);

    cout << (iamFirst ? "First" : "Second") << '\n' << flush;
    int64 K = hugeK;                     // 直前手の取り量（初手は∞）

    while (true) {
        if (!iamFirst) {                 // 先手でなければ相手の着手を読む
            int idx, x;                  // 1‑based
            if (!(cin >> idx >> x)) return 0;
            A[idx-1] -= x;               // 山を更新
            K = x;                       // 新しい制限
            int ret; cin >> ret;         // Interactor の OK (=0)
            if (ret) return 0;
        }

        // ---------- 自分の手を探す ----------
        int64 P = next_pow2(K);
        int64 g  = nim_xor(P);

        int sel = -1, take = -1;

        if (g != 0) {
            // 「勝ち局面」なので取れる手を探す
            for (int i = 0; i < N && sel==-1; ++i) {
                int64 r = A[i] % P;          // その山のブロック内値
                // 取り量を 1..min(A[i],K) で全探索（十分小さい）
                int upper = min<int64>(A[i], K);
                for (int x = 1; x <= upper; ++x) {
                    int64 newK = x;
                    int64 P2   = next_pow2(newK);
                    int64 nxor = 0;
                    for (int j = 0; j < N; ++j) {
                        int64 val = (j==i) ? (A[j]-x) : A[j];
                        nxor ^= (val % P2);
                    }
                    if (nxor == 0) {          // 相手を負け局面へ
                        sel  = i;
                        take = x;
                        break;
                    }
                }
            }
        }

        if (sel == -1) {   // g==0 か「探索で見つからず」
            // K=1 ゲーム（偶奇ゲーム）に帰着させる
            for (int i = 0; i < N; ++i)
                if (A[i] && 1 <= K) {         // 常に成立
                    sel  = i;
                    take = 1;
                    break;
                }
        }

        // ----------- 出力して山を更新 -------------
        cout << (sel + 1) << ' ' << take << '\n' << flush;
        A[sel] -= take;
        K = take;

        int ret; cin >> ret;
        if (ret) return 0;        // interactor が 0 以外なら終了

        iamFirst = false;         // 2 手目以降は常に後手扱い
    }
}
0