結果

問題 No.3120 Lower Nim
ユーザー keigo kuwata
提出日時 2025-04-24 14:52:31
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,429 bytes
コンパイル時間 2,020 ms
コンパイル使用メモリ 195,472 KB
実行使用メモリ 25,972 KB
平均クエリ数 2233.55
最終ジャッジ日時 2025-04-24 14:52:42
合計ジャッジ時間 9,568 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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;

    bool ourTurn = isFirst;
    while(true){
        int i, x, ret;
        if(!ourTurn){
            // 相手の手番を読む
            cin >> i >> x;
            cin >> ret;
            if(ret == -1) return 0;  // 敗北
            --i;
            A[i] -= x;
            K = x;
        }

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

        // 1) 通常の Nim の要領で 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) 上記ができない場合は、まず可能なら上限 K を丸取り
        if(move_i == -1){
            for(int j = 0; j < N; j++){
                if(A[j] >= K){
                    move_i = j;
                    move_x = K;
                    break;
                }
            }
        }

        // 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)    // ret=1 で勝利、ret=-1 で敗北
            return 0;
        K = move_x;
        ourTurn = false;
    }

    return 0;
}
0