← Real problems

yac6p4

easygamesgrundyStatement on DMOJ

CP Lang

12 lines0.3 spec
// yac6p4: Sprague-Grundy. The piles XOR to `need`; the answer is the least pile size up to `m`
// whose Grundy value is `need`, so adding it hands the opponent a zero position.
const grundy: [0..=100]Int = [
    0, 0, 1, 2, 2, 7, 3, 5, 4, 5, 10, 9, 9, 15, 5, 12, 14, 17, 15, 17, 17, 23, 24, 27, 22, 34,
    18, 28, 41, 29, 21, 34, 33, 41, 26, 55, 30, 42, 35, 39, 34, 56, 65, 39, 41, 47, 45, 43, 40,
    40, 29, 44, 58, 56, 52, 57, 55, 54, 55, 48, 61, 60, 60, 58, 44, 67, 67, 64, 64, 37, 66, 64,
    74, 70, 72, 47, 66, 75, 74, 73, 90, 81, 79, 80, 78, 81, 87, 95, 95, 83, 124, 92, 93, 86, 67,
    91, 97, 88, 97, 100, 103,
]
let (n, m) = read<(1..=200_000, 1..=100)>()
let need = read<[n]0..=100>().map(x => grundy[x]).fold((x, y) => x ^ y, 0)
print((1..=m).find(i => grundy[i] == need) ?? -1)

Accepted C++

65 lines · 8.63 s on the judge
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

constexpr int vals[101] = {
    0,  0,  1,  2,  2,  7,   3,  5,  4,  5,  10, 9,  9,  15, 5,   12, 14,
    17, 15, 17, 17, 23, 24,  27, 22, 34, 18, 28, 41, 29, 21, 34,  33, 41,
    26, 55, 30, 42, 35, 39,  34, 56, 65, 39, 41, 47, 45, 43, 40,  40, 29,
    44, 58, 56, 52, 57, 55,  54, 55, 48, 61, 60, 60, 58, 44, 67,  67, 64,
    64, 37, 66, 64, 74, 70,  72, 47, 66, 75, 74, 73, 90, 81, 79,  80, 78,
    81, 87, 95, 95, 83, 124, 92, 93, 86, 67, 91, 97, 88, 97, 100, 103};

void solve() {
    int n, m;
    cin >> n >> m;
    int arr[n];
    for (auto& a : arr) {
        cin >> a;
    }
    int cv = 0;
    for (auto& a : arr) {
        cv ^= vals[a];
    }
    for (int i = 1; i <= m; i++) {
        if (!(cv ^ vals[i])) {
            cout << i << endl;
            return;
        }
    }
    cout << -1 << endl;
}

int main() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
    solve();
}