結果

問題 No.3120 Lower Nim
コンテスト
ユーザー shibh308
提出日時 2025-04-20 19:39:10
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 246 ms / 2,000 ms
コード長 2,433 bytes
コンパイル時間 2,326 ms
コンパイル使用メモリ 194,780 KB
実行使用メモリ 26,356 KB
平均クエリ数 2460.66
最終ジャッジ日時 2025-04-20 19:39:21
合計ジャッジ時間 10,500 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

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 とみなす
    int64 K = (int64)1e18;

    // 初期 XOR を見て先攻/後攻を決定
    int64 initialXor = 0;
    for (auto v : A) initialXor ^= v;
    bool myTurn = (initialXor != 0);
    cout << (myTurn ? "First\n" : "Second\n") << flush;

    while (true) {
        // ── 相手の手を読む ──
        if (!myTurn) {
            int  j;
            int64 y;
            if (!(cin >> j >> y)) return 0;
            A[j-1] -= y;
            K = y;
            int judge; 
            cin >> judge;
            if (judge != 0) break;
            myTurn = true;
        }

        // ── 自分の手を決める (O(N + log K)) ──
        int64 P    = next_pow2(K);
        int64 mask = P - 1;

        // 現局面の “mod P した 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) {
            for (int i = 0; i < N; i++) {
                int64 r = A[i] & mask;    // A[i] mod P
                int64 t = r ^ g;          // こうすれば xor=0 になる余り
                int64 x = r - t;          // 実際に取る数
                if (t < r && 1 <= x && x <= K) {
                    sel  = i;
                    take = x;
                    break;
                }
            }
        }

        // 負け局面 or “罠” 局面なら石1個だけ取る
        if (sel == -1) {
            for (int i = 0; i < N; i++) {
                if (A[i] > 0) {
                    sel  = i;
                    take = 1;
                    break;
                }
            }
        }

        // ── 着手の出力＆更新 ──
        cout << (sel + 1) << " " << take << "\n" << flush;
        A[sel] -= take;
        K = take;

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

    return 0;
}
0