Game, pretty good problem
The key is that when one player wants to change to a winning state, the other player will change the advantage back
So don't consider changing to a winning state anymore, just greedily take what you can have at the moment
Divide into groups with 1 stone and groups with multiple stones
When all groups with 1 stone are taken, add up the number of stones in the groups with multiple stones. The parity of the sum can determine who the whole group belongs to
Of course, as mentioned before, when you want to change the parity, the other player can also change it back
// BEGIN CUT HERE
// END CUT HERE
#line 5 "GCAcode.cpp"
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string\>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
using namespace std;
#ifdef DEBUG
#define VAR(a,b) \_\_typeof(b) a=(b)
#define debug(...) printf("DEBUG: "),printf(\_\_VA\_ARGS\_\_)
#else
#define VAR(a,b) \_\_typeof(b) a=(b)
#define debug(...)
#endif
typedef unsigned int uint;
typedef long long int Int;
typedef unsigned long long int UInt;
#define Set(a,s) memset(a,s,sizeof(a))
#define Pln() printf("\\n")
#define For(i,x)for(int i=0;i<x;i++)
#define CON(x,y) x##y
#define M 55
#define PB push\_back
#define oo INT\_MAX
#define FOR(a,b) for(VAR(a,(b).begin());a!=(b).end();++a)
#define eps 1e-9
#define X first
#define Y second
inline bool xdy(double x,double y){return x>y+eps;}
inline bool xddy(double x,double y){return x>y-eps;}
inline bool xcy(double x,double y){return x<y-eps;}
inline bool xcdy(double x,double y){return x<y+eps;}
const Int mod=1000000007;
struct chest{
int s,v;
}chests\[M\];
bool cmp(chest a,chest b){
if(a.s==b.s)return a.v>b.v;
return a.s<b.s;
}
class StoneGame
{
public:
int getScore(vector <int\> treasure, vector <int\> stones){
int n=treasure.size();
for(int i=0;i<n;i++){
chests\[i\].s=stones\[i\];
chests\[i\].v=treasure\[i\];
}
sort(chests,chests+n,cmp);
int oneg=0;
int muls=0;
int mulg=0;
for(int i=0;i<n;i++){
if(chests\[i\].s==1)oneg++;
else{
muls+=chests\[i\].s;
mulg+=chests\[i\].v;
}
}
int ans=0;
for(int i=0;i<n;i+=2){
if(chests\[i\].s==1)ans+=chests\[i\].v;
else break;
}
if(oneg%2==0){
if(muls&1)ans+=mulg;
}else{
if(muls%2==0)ans+=mulg;
}
return ans;
}
// BEGIN CUT HERE
public:
void run\_test(int Case) {
if ((Case == -1) || (Case == 0)) test\_case\_0();
if ((Case == -1) || (Case == 1)) test\_case\_1();
if ((Case == -1) || (Case == 2)) test\_case\_2();
if ((Case == -1) || (Case == 3)) test\_case\_3();
if ((Case == -1) || (Case == 4)) test\_case\_4();
if ((Case == -1) || (Case == 5)) test\_case\_5();
}
private:
template <typename T> string print\_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const\_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\\"' << \*iter << "\\","; os << " }"; return os.str(); }
void verify\_case(int Case, const int &Expected, const int &Received) { cout << "Test Case #" << Case << "..."; if (Expected == Received) cout << "PASSED" << endl; else { cout << "FAILED" << endl; cout << "\\tExpected: \\"" << Expected << '\\"' << endl; cout << "\\tReceived: \\"" << Received << '\\"' << endl; } }
void test\_case\_0() {
int Arr0\[\] = {3,2};
vector <int\> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0\[0\])));
int Arr1\[\] = {1,2};
vector <int\> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1\[0\])));
int Arg2 = 5;
verify\_case(0, Arg2, getScore(Arg0, Arg1)); }
void test\_case\_1() {
int Arr0\[\] = {5,4,3,2,1};
vector <int\> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0\[0\])));
int Arr1\[\] = {1,1,1,1,1};
vector <int\> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1\[0\])));
int Arg2 = 9;
verify\_case(1, Arg2, getScore(Arg0, Arg1)); }
void test\_case\_2() {
int Arr0\[\] = {5,5};
vector <int\> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0\[0\])));
int Arr1\[\] = {2,2};
vector <int\> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1\[0\])));
int Arg2 = 0;
verify\_case(2, Arg2, getScore(Arg0, Arg1)); }
void test\_case\_3() {
int Arr0\[\] = {1};
vector <int\> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0\[0\])));
int Arr1\[\] = {10};
vector <int\> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1\[0\])));
int Arg2 = 0;
verify\_case(3, Arg2, getScore(Arg0, Arg1)); }
void test\_case\_4() {
int Arr0\[\] = {3,2};
vector <int\> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0\[0\])));
int Arr1\[\] = {1,2};
vector <int\> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1\[0\])));
int Arg2 = 5;
verify\_case(4, Arg2, getScore(Arg0, Arg1)); }
void test\_case\_5() {
int Arr0\[\] = {3,2};
vector <int\> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0\[0\])));
int Arr1\[\] = {1,2};
vector <int\> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1\[0\])));
int Arg2 = 5;
verify\_case(5, Arg2, getScore(Arg0, Arg1)); }
// END CUT HERE
};
// BEGIN CUT HERE
int main()
{
StoneGame \_\_\_test;
\_\_\_test.run\_test(-1);
return 0;
}
// END CUT HERE