結果

問題 No.3120 Lower Nim
ユーザー keigo kuwata
提出日時 2025-04-24 14:51:34
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,628 bytes
コンパイル時間 2,220 ms
コンパイル使用メモリ 195,836 KB
実行使用メモリ 26,072 KB
平均クエリ数 2233.55
最終ジャッジ日時 2025-04-24 14:51:45
合計ジャッジ時間 10,302 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 39 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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

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

    // ∑A_i ≤10000 なので、初期Kは10001で十分
    int K = 10001;

    // 山の XOR を返す
    auto calcXor = [&](){
        int s = 0;
        for(int v : A) s ^= v;
        return s;
    };

    // 初期 XOR で先手か後手かを決定
    int S = calcXor();
    bool isFirst = (S != 0);
    cout << (isFirst ? "First\n" : "Second\n") << flush;

    // 直前のジャッジ（相手）の手を覚えておく
    int last_i = -1, last_x = -1;
    // ourTurn は最初だけ使う（以降は常に judge→us のサイクル）
    bool ourTurn = isFirst;

    while(true){
        int ret, i, x;
        // 相手の手を読む
        if(!ourTurn){
            cin >> i >> x;
            cin >> ret;
            if(ret == -1) return 0;    // 負け確定
            --i;
            A[i] -= x;
            K = x;
            last_i = i;
            last_x = x;
        }

        // 自分の手番
        S = calcXor();
        int move_i = -1, move_x = 1;

        // 1) 先手か、XOR≠0 のとき：XORを0に戻す手があれば取る
        if(S != 0){
            for(int j = 0; j < N; j++){
                int a = A[j];
                int t = a ^ S;
                if(t < a){
                    int r = a - t;
                    if(r <= K){
                        move_i = j;
                        move_x = r;
                        break;
                    }
                }
            }
        }

        // 2) 調整手が取れない（または Xor=0 のとき）：ミラー戦略
        if(move_i == -1 && last_i != -1 && last_x <= K && A[last_i] >= last_x){
            // 相手が直前に(i_last, x_last)を取ったら、同じ山から同じ x_last を取る
            move_i = last_i;
            move_x = last_x;
        }

        // 3) ミラーもできないなら、とりあえず 1 石だけ
        if(move_i == -1){
            for(int j = 0; j < N; j++){
                if(A[j] > 0){
                    move_i = j;
                    move_x = 1;
                    break;
                }
            }
        }

        // 手を出力
        A[move_i] -= move_x;
        cout << (move_i + 1) << " " << move_x << "\n" << flush;

        // 結果を読む
        cin >> ret;
        if(ret != 0) return 0;  // ret=1 で勝利, ret=-1 で敗北
        K = move_x;
        ourTurn = false;
    }

    return 0;
}
0