結果

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

ソースコード

diff # 

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

// k を超える最小の 2 の冪を返す
int64 next_pow2(int64 k) {
    int64 p = 1;
    while (p <= k) p <<= 1;
    return p;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int64> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    // 初手用の大きな K (山の総数 <= 10^4 なので十分)
    int64 K = (int64)1e18;

    // 初回の P, mask, XOR を計算して先攻/後攻を決める
    {
        int64 P    = next_pow2(K);
        int64 mask = P - 1;
        int64 g    = 0;
        for (int i = 0; i < N; i++) {
            g ^= (A[i] & mask);
        }
        if (g != 0) {
            cout << "First\n" << flush;
        } else {
            cout << "Second\n" << flush;
        }
    }

    bool myTurn = false;
    {
        // 再度同じ XOR を計算して myTurn を初期化
        int64 P    = next_pow2(K);
        int64 mask = P - 1;
        int64 g    = 0;
        for (int i = 0; i < N; i++) g ^= (A[i] & mask);
        myTurn = (g != 0);
    }

    // --- インタラクティブなやり取りループ ---
    while (true) {
        // (1) 相手の手を読む
        if (!myTurn) {
            int j;
            int64 y;
            if (!(cin >> j >> y)) return 0;
            // 山 j から y を取られた
            A[j - 1] -= y;
            K = y;
            int judge;
            cin >> judge;
            if (judge != 0) return 0;
        }

        // (2) 自分の手を決める (O(N + log K))
        int64 P    = next_pow2(K);
        int64 mask = P - 1;
        // 現局面の Nim XOR
        int64 g = 0;
        for (int i = 0; i < N; i++) {
            g ^= (A[i] & mask);
        }

        int sel = -1;
        int64 take = 0;

        if (g != 0) {
            // 勝ち局面 → 取り量 x は一意に決まる
            // g の最上位ビットを取り出す
            int shift = 63 - __builtin_clzll(g);
            int64 hb  = 1LL << shift;
            for (int i = 0; i < N; i++) {
                int64 r = A[i] & mask;
                if (r & hb) {
                    // x = r - (r xor g)
                    sel  = i;
                    take = r - (r ^ g);
                    break;
                }
            }
            // (必ず見つかる)
        }

        if (sel == -1) {
            // g==0 の負け局面なら，石 1 個だけ取るフォールバック
            for (int i = 0; i < N; i++) {
                if (A[i] > 0) {
                    sel  = i;
                    take = 1;
                    break;
                }
            }
        }

        // (3) 出力→更新
        cout << (sel + 1) << " " << take << "\n" << flush;
        A[sel] -= take;
        K = take;

        int judge;
        cin >> judge;
        if (judge != 0) break;

        // ２手目以降は常に後手として振る舞う
        myTurn = false;
    }

    return 0;
}
0