ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1540. Battle for the Ring

WA6
Posted by chenyushuo 3 Apr 2015 17:59
Could you give me some tests to train my code? I WA in test 6 many times and I don't know why anymore.. I need some people to help me.
Here is my code:
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
int sg[55][110][110];
int a[110][110];
int n;
bool v[110], l[110];
int mex ( int l, int r, int x ){
    if ( sg[x][l][r] != -1 ) return sg[x][l][r];
    if ( l > r ) return 0;
    int i, j, k;
    int p, ss;
    memset ( v, false, sizeof (v) );
    for ( i = l; i <= r; i ++ ){
        p = a[x][i]; ss = 0;
        k = l;
        for ( j = l; j <= r; j ++ ){
            if ( a[x][j] <= p ){
                ss ^= mex ( k, j-1, x );
                k = j+1;
            }
        }
        ss ^= mex ( k, r, x );
        v[ss] = true;
    }
    for ( i = 0; ; i ++ ){
        if ( v[i] == false ){
            sg[x][l][r] = i;
            return i;
        }
    }
}
int get_sg ( int x ){
    int i, j, k;
    for ( i = 1; i <= a[x][0]; i ++ ) sg[x][i][i] = 1;
    return mex ( 1, a[x][0], x );
}
void get_way ( int ans ){
    int i, j, k, x, y, o;
    int p, s;
    for ( i = 1; i <= n; i ++ ){
        for ( j = 1; j <= a[i][0]; j ++ ){
            p = a[i][j]; s = 0;
            o = 1;
            for ( k = 1; k <= a[i][0]; k ++ ){
                if ( a[i][k] <= p ){
                    s ^= mex ( o, k-1, i );
                    o = k+1;
                }
            }
            s ^= mex ( o, a[i][0], i );
            if ( (ans^sg[i][1][a[i][0]]^s) == 0 ){
                printf ( "%d %d\n", i, j );
                return;
            }
        }
    }
}
int main (){
    int i, j, k;
    scanf ( "%d", &n );
    k = 0;
    memset ( sg, -1, sizeof (sg) );
    for ( i = 1; i <= n; i ++ ){
        scanf ( "%d", &a[i][0] );
        for ( j = 1; j <= a[i][0]; j ++ ) scanf ( "%d", &a[i][j] );
        get_sg (i);
        k ^= sg[i][1][a[i][0]];
    }
    if ( k == 0 ) printf ( "S\n" );
    else{
        printf ( "G\n" );
        get_way (k);
    }
    return 0;
}