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

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

WA 5
Послано MarioYC 16 янв 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;
}