結果

問題 No.3090 NimNim
ユーザー zawakasu
提出日時 2025-04-05 13:59:51
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 67 ms / 2,000 ms
コード長 1,677 bytes
コンパイル時間 961 ms
コンパイル使用メモリ 91,772 KB
実行使用メモリ 5,888 KB
最終ジャッジ日時 2025-04-05 13:59:55
合計ジャッジ時間 3,681 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"



#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa

#include <concepts>
#include <iterator>

namespace zawa {

enum class GameWinner {
    First,
    Second,
};

template <std::input_iterator It>
GameWinner MisereNim(It first, It last) {
    u64 grundy = 0;
    usize size = 0;
    bool over2 = false;
    for (auto it = first ; it != last ; it++, size++) {
        u64 val = static_cast<u64>(*it);
        over2 |= val >= 2;
        grundy ^= val;
    }
    if (over2) return grundy ? GameWinner::First : GameWinner::Second;
    else return size & 1 ? GameWinner::Second : GameWinner::First;
}

} // namespace zawa

#include <algorithm>
#include <iostream>

using namespace zawa;
int N, M, A[100010], B[100010];
bool solve() {
    std::cin >> N >> M;
    for (int i = 0 ; i < N ; i++) std::cin >> A[i];
    for (int i = 0 ; i < M ; i++) std::cin >> B[i];
    if (MisereNim(A, A + N) == GameWinner::First) {
        return true;
    }
    else {
        int max = *std::max_element(A, A + N);
        if (max >= 2) {
            return false;
        }
        else {
            int x = 0;
            for (int i = 0 ; i < M ; i++) x ^= B[i];
            return x != 0;
        }
    }
}

int main() {
#ifdef ONLINE_JUDGE
    std::cout << (solve() ? "First\n" : "Second\n");
#else
    std::cout << "Hello World\n";
#endif
}
0