1686. Stone Game VI

Alice and Bob take turns playing a game, with Alice starting first.

There are n stones in a pile. On each player’s turn, they can remove a stone from the pile and receive points based on the stone’s value. Alice and Bob may value the stones differently.

You are given two integer arrays of length n, aliceValues and bobValues. Each aliceValues[i] and bobValues[i] represents how Alice and Bob, respectively, value the ith stone.

The winner is the person with the most points after all the stones are chosen. If both players have the same amount of points, the game results in a draw. Both players will play optimally. Both players know the other’s values.

Determine the result of the game, and:

• If Alice wins, return 1.
• If Bob wins, return -1.
• If the game results in a draw, return 0.

class Solution {
public:
    int stoneGameVI(vector<int>& A, vector<int>& B) {
        vector<array<int,3>> stone;
        for(int i = 0; i < A.size(); i++) {
            stone.push_back({A[i] + B[i], A[i], B[i]});
        }
        sort(rbegin(stone), rend(stone));
        int a = accumulate(begin(A), end(A), 0), b = accumulate(begin(B), end(B), 0);
        for(int i = 0; i < stone.size(); i++) {
            auto [s, al, bo] = stone[i];
            if(i & 1) a -= al;
            else b -= bo;
        }
        return a == b ? 0 : a > b ? 1 : -1;
    }
};