Test/yukicoder/3090.test.cpp

View this file on GitHub
Last update: 2025-04-05 14:16:27+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
Link: https://yukicoder.me/submissions/1064971

Depends on

Code

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

/*
 * yukicoder No.3090 NimNim
 * https://yukicoder.me/submissions/1064971
 */

#include "../../Src/Utility/MisereNim.hpp"

#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
}

#line 1 "Test/yukicoder/3090.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

/*
 * yukicoder No.3090 NimNim
 * https://yukicoder.me/submissions/1064971
 */

#line 2 "Src/Utility/MisereNim.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#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
#line 4 "Src/Utility/MisereNim.hpp"

#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
#line 9 "Test/yukicoder/3090.test.cpp"

#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
}