1839E - Decreasing Game - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

const int NAX = 90010;

vector<bool> check(const vector<int> &a) {
    const int n = a.size();
    vector<bitset<NAX>> dp(n + 1);
    const int sum = accumulate(a.begin(), a.end(), 0);
    dp[0].set(0);
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i - 1] | (dp[i - 1] << (a[i - 1] << 1));
    }
    const int target = sum;
    if (!dp[n][target]) {
        return vector<bool>();
    }
    int now = target;
    vector<bool> ans(n);
    for (int i = n - 1; i >= 0; i--) {
        int x = a[i] << 1;
        if (now - x >= 0 && dp[i][now - x]) {
            now -= x;
            ans[i] = true;
        } else {
            assert(dp[i][now]);
            ans[i] = false;
        }
    }
    return ans;
}

void make_move(vector<int> &a, int i, int j) {
    int m = min(a[i], a[j]);
    a[i] -= m;
    a[j] -= m;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector<bool> b = check(a);
    if (b.size()) {
        cout << "Second" << endl;
        while (true) {
            int i;
            cin >> i;
            if (i == 0) {
                break;
            }
            assert(a[i] > 0);
            bool sign = b[i];
            int w = -1;
            for (int j = 1; j <= n; j++) {
                if (j != i && a[j] > 0 && b[j] != sign) {
                    w = j;
                    break;
                }
            }
            cout << w << endl;
            make_move(a, i, w);
        }
    } else {
        cout << "First" << endl;
        while (true) {
            int my_move = -1;
            for (int i = 1; i <= n; i++) {
                if (a[i] != 0) {
                    my_move = i;
                    break;
                }
            }
            cout << my_move << endl;
            int j;
            cin >> j;
            if (j == 0) {
                break;
            }
            make_move(a, my_move, j);
        }
    }
}