|
|
back to boardWA 5 Posted by MarioYC 16 Jan 2012 15:44 Hi, I'm using grundy numbers for this problems, however I get WA 5. #include <cstdio> #include <cstring> using namespace std; int n[50],a[50][100]; int g[50][100][100]; int main(){ int K;
scanf("%d",&K);
for(int i = 0;i < K;++i){ scanf("%d",&n[i]);
for(int j = 0;j < n[i];++j) scanf("%d",&a[i][j]); }
memset(g,0,sizeof g);
bool have[201];
for(int k = 0;k < K;++k){ for(int l = 1;l <= n[k];++l){ for(int i = 0;i + l <= n[k];++i){ memset(have,false,sizeof have);
for(int j = i;j < i + l;++j){ int x = a[k][j],sum = 0;
for(int s = i;s < i + l;){ if(a[k][s] <= x) ++s; else{ int e = s;
while(e < i + l && a[k][e] > x) ++e;
sum ^= g[k][s][e - 1]; s = e + 1; } }
have[sum] = true; }
while(have[ g[k][i][i + l - 1] ]) ++g[k][i][i + l - 1]; } } }
int G = 0;
for(int k = 0;k < K;++k) G ^= g[k][0][n[k] - 1];
if(G){ puts("G");
bool found = false;
for(int k = 0;k < K && !found;++k){ for(int i = 0;i < n[k] && !found;++i){ G = 0;
for(int j = 0;j < K;++j) if(j != k) G ^= g[k][0][n[j] - 1];
int x = a[k][i],sum = 0;
for(int s = 0;s < n[k];){ if(a[k][s] <= x) ++s; else{ int e = s;
while(e < n[k] && a[k][e] > x) ++e;
G ^= g[k][s][e - 1]; s = e + 1; } }
if(G == 0){ found = true; printf("%d %d\n",k + 1,i + 1); } } } }else puts("S");
return 0; } |
|
|