結果

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

ソースコード

diff # 

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
//#include<atcoder/all>
//using namespace atcoder;
using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
constexpr ll MAX = 2000000000000000000;
constexpr ld PI = 3.14159265358979;
constexpr ll MOD = 0;//2024948111;
ld dotorad(ld K){ return PI * K / 180.0; }
ld radtodo(ld K){ return K * 180.0 / PI; }
mt19937 mt;
void randinit(){ srand((unsigned)time(NULL));mt = mt19937(rand()); }
int main(){
    ll N;
    cin >> N;
    vector<ll> A(N);
    for(ll i = 0; i < N; i++){
        cin >> A[i];
    }
    ll s = 0,s2 = 0;
    for(ll i = 0;i < N;i++){
        s ^= A[i];
        s2 += A[i];
    }
    ll p = 0;
    ll K = MAX;

    if(s2 % 2 == 1){
        cout << "First" << endl;
        s = -1;
        K = 1;
    }
    else if(s == 0){
        cout << "Second" << endl;
        p = 1;
    }
    else{
        cout << "First" << endl;
    }
    set<tuple<ll,ll>> st;
    for(ll i = 0;i < N;i++){
        st.emplace(A[i],i);
    }
    while(1){
        if(p == 1){
            ll i,p;
            cin >> i >> p;
            i--;
            auto it = st.find(make_tuple(A[i],i));
            st.erase(it);
            if(s != -1) s ^= A[i];
            A[i] -= p;
            if(s != -1) s ^= A[i];
            st.emplace(A[i],i);
            K = p;
            s2 -= p;
            if(s2 % 2 == 1) s = -1;
        }
        else{
            ll id = -1,x = MAX;
            auto p = st.rbegin();
            if(s != -1) {
                while(p != st.rend()){
                    auto [a,i] = *p;
                    ll disired_nokori = (A[i] ^ s);
                    if(disired_nokori < A[i]){
                        ll kesu = A[i] - disired_nokori;
                        if(kesu <= K && x > kesu){
                            x = kesu;
                            id = i;
                        }
                    }
                    p++;
                }
            }

            if(id == -1){
                auto p = st.rbegin();
                while(p != st.rend()){
                    auto [a,i] = *p;
                    if(0 < A[i]){
                        ll kesu = 1;
                        if(kesu <= K){
                            x = kesu;
                            id = i;
                            break;
                        }
                    }
                    p++;
                }
                s = -1;
            }

            auto it = st.find(make_tuple(A[id],id));
            st.erase(it);
            cout << id + 1 << " " << x << endl;
            if(s != -1) s ^= A[id];
            A[id] -= x;
            s2 -= x;
            st.emplace(A[id],id);
            if(s != -1) s ^= A[id];
            K = x;
        }
        ll ret;
        cin >> ret;
        if(ret != 0) return 0;
        p ^= 1;
    }
}
0