ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1540. Битва за кольцо

WA6
Послано chenyushuo 3 апр 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;
}