POI Task Game

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int m, n; cin >> m >> n;
    vector<pair<int, int>> groups;
    for (int i = 0; i < n; ++i) {
        int x; cin >> x;
        if (!groups.empty() && groups.back().second + 1 == x) ++groups.back().second;
        else groups.emplace_back(x, x);
    }

    if (groups.back().second == m-1) {
        cout << groups.back().second - groups.back().first + 1 << endl;
        return 0;
    }

    int k = groups.size();
    vector<bool> evenGroup(groups.size());
    groups.emplace_back(m, m);
    evenGroup.push_back(true);

    int XOR = 0;
    for (int i = k-1; i >= 0; --i) {
        evenGroup[i] = evenGroup[i+1] ^ ((groups[i+1].first - groups[i].second + 1) & 1);
        if (evenGroup[i]) XOR = XOR ^ (groups[i].second-groups[i].first+1);
    }
    if (XOR == 0) {
        cout << 0 << endl;
        return 0;
    }

    int winningMoves = 0;
    for (int i = 0; i < k; ++i) {
        if (evenGroup[i]) {
            int curSize = (groups[i].second-groups[i].first+1);
            int newSize = curSize ^ XOR; // to make XOR == 0
            if (newSize < curSize) ++winningMoves;
            else if (newSize > curSize) {
                // previous (odd) group needs to be non-empty and have at least new-cur
                if (groups[i-1].second+2 == groups[i].first &&
                    groups[i-1].second-groups[i-1].first+1 >= newSize-curSize) ++winningMoves;
            }
        } else {
            // add case where next group is even and empty
            int curSize = (groups[i].second-groups[i].first+1);
            if (curSize >= XOR && groups[i].second+2 < groups[i+1].first) ++winningMoves;
        }
    }
    cout << winningMoves << endl;
    return 0;
}