Can’t figure out the issue in my solution … keep getting WA…
dp[i] - represents the answer for state i
Code below
Blockquote
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include<string.h>
#include
#include<memory.h>
#include
#include
#include<unordered_map>
#include<unordered_set>
#pragma comment(linker, “/stack:30000000”)
using namespace std;
#define For(i,l,r) for (int i = l ;i <=r ; ++ i )
#define ForI(it , s , T) for (T :: iterator it = s.begin(); it != s.end() ; ++ it )
#define LL long long
#define iinf 2000000000
#define linf 10000000000000000LL
#define MOD 1000000007LL
#define Pi 3.1415926535897932384
#define bit(mask,i) ((mask>>i)&1)
#define pb(x) push_back(x)
#define mk(x,y) make_pair(x,y)
#define sqr(x) ((x)*(x))
#define pause cin.get();cin.get();
#define fir first
#define sec second
#define ln(x) log(x)
#define pi pair<int,int>
#define MAX 510
using namespace std;
int player1[13], player2[13];
int dp[1600000];
void clear() {
for(int i =0;i< 13;i++) player1[i] = player2[i] = 0;
}
int getNextState(int x, int y, int z, int state) {
int a[13], temp = state;
for(int i = 0;i < 13;i ++) {
a[i] = temp % 3;
temp = temp / 3;
}
a[x]--;
a[y]--;
a[z]--;
int ans = 0;
for(int i = 12;i >= 0;i--) ans = ans * 3 + a[i];
return ans;
}
int rec(int state) {
if(state == 0) return 0;
if(dp[state]!=-1) return dp[state];
int a[13], temp = state;
for(int i = 0;i < 13;i ++) {
a[i] = temp % 3;
temp = temp / 3;
}
int ans = 0;
for(int i = 0;i < 13 ;i++)
for(int j = i;j <13;j++)
for(int k = j;k < 13;k++) {
if(i == j && j ==k) continue;
if(a[i] && a[j] && a[k]) {
if(i + j > k) {
if((i == j && a[i] == 2) || (j == k && a[j] == 2))
ans = max(ans,1 + rec(getNextState(i, j, k, state)));
if(i != j && j != k)
ans = max(ans,1 + rec(getNextState(i, j, k, state)));
}
}
}
return dp[state] = ans;
}
int main()
{
int n,x;
memset(dp, -1, sizeof(dp) );
while(1) {
clear();
cin>>n;
if(!n) break;
For(i,0,n-1) {
cin>>x;
if(i%2 == 0) player1[x-1] ++;
else player2[x-1]++;
}
int perfectTriple1 = 0, perfectTriple2 = 0;
for(int i = 0; i< 13;i++) {
perfectTriple1 += player1[i] / 3;
perfectTriple2 += player2[i] / 3;
player1[i] = player1[i] % 3;
player2[i] = player2[i] % 3;
}
if(perfectTriple1 != perfectTriple2) {
cout<<(perfectTriple1 > perfectTriple2 ? "1" : "2")<<endl;
}
else {
int player1State = 0, player2State = 0;
for(int i = 12;i >= 0; i--) {
player1State = player1State * 3 + player1[i];
player2State = player2State * 3 + player2[i];
}
//cout<<player1State<<" "<<player2State<<endl;
int commonTripples1 = rec(player1State);
int commonTripples2 = rec(player2State);
//cout<<commonTripples1<<" "<<commonTripples2<<endl;
if(commonTripples1 == commonTripples2)
cout<<"0"<<endl;
else
cout<<(commonTripples1 > commonTripples2 ? "1" : "2")<<endl;
}
}
return 0;
}