Cod sursă (job #143340)

#include <cstdio>

using namespace std;
struct ecu
{
    int inf;
    ecu *urm;
    ecu(int v)
    {
        inf=v;
        urm=0;
    }
};
ecu *p[1000010],*last,*aux,*s[1002],*es,*ep;
int n,i,j,k,m,Inf,x[1002][1002],sol[1000010];
int main()
{
    freopen("switch5.in","r",stdin);
    freopen("switch5.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            x[i][j]=++k;
    for(i=1;i<n;i++)
        for(j=1;j<=n;j++)
        {
            m=x[i][j];
            last=new ecu(x[i][j]);
            p[m]=last;
            if(x[i+1][j-1]){aux=new ecu(x[i+1][j-1]);last->urm=aux;last=aux;}
            aux=new ecu(x[i+1][j]);last->urm=aux;last=aux;
            if(x[i+1][j+1]){aux=new ecu(x[i+1][j+1]);last->urm=aux;last=aux;}
            if(x[i+2][j]){aux=new ecu(x[i+2][j]);last->urm=aux;last=aux;}
            aux=new ecu(n*n+1);last->urm=aux;last=aux;
        }
    last=new ecu(x[1][1]);s[1]=last;
    aux=new ecu(x[1][2]);last->urm=aux;last=aux;
    aux=new ecu(x[2][1]);last->urm=aux;last=aux;
    aux=new ecu(n*n+1);last->urm=aux;last=aux;
    for(j=2;j<n;j++)
    {
        last=new ecu(x[1][j-1]);s[j]=last;
        aux=new ecu(x[1][j]);last->urm=aux;last=aux;
        aux=new ecu(x[1][j+1]);last->urm=aux;last=aux;
        aux=new ecu(x[2][j]);last->urm=aux;last=aux;
        aux=new ecu(n*n+1);last->urm=aux;last=aux;
    }
    last=new ecu(x[1][n-1]);s[1]=last;
    aux=new ecu(x[1][n]);last->urm=aux;last=aux;
    aux=new ecu(x[2][n]);last->urm=aux;last=aux;
    aux=new ecu(n*n+1);last->urm=aux;last=aux;
    for(i=1;i<=n;i++)
    {
        //rezolv ecuatii secundare
        while(s[i]&&p[s[i]->inf])
        {
            es=s[i];s[i]=0;last=0;
            ep=p[es->inf];
            for(;ep&&es;)
            {
                if(es->inf==ep->inf)
                {
                    aux=es;es=es->urm;delete(aux);
                    ep=ep->urm;
                    continue;
                }
                if(es->inf<ep->inf){Inf=es->inf;aux=es;es=es->urm;delete aux;}
                else {Inf=ep->inf;ep=ep->urm;}
                aux=new ecu(Inf);
                if(!last){last=aux;s[i]=aux;}
                else {last->urm=aux;last=aux;}

            }
            if(ep)
                for(;ep;ep=ep->urm)
                {
                    aux=new ecu(ep->inf);
                    if(!last){last=aux;s[i]=aux;}
                    else {last->urm=aux;last=aux;}
                }
            else
                if(es)
                {
                    if(!last){s[i]=es;}
                    else last->urm=es;
                }
        }
        if(s[i])p[s[i]->inf]=s[i];
    }
    sol[n*n+1]=1;
    for(i=k;i;i--)
        if(p[i])
        {
            for(aux=p[i]->urm;aux;aux=aux->urm)
                sol[i]^=sol[aux->inf];
        }
    for(i=1,k=0;i<=n;i++)
    {
        for(j=1;j<=n;j++)
            printf("%d",sol[++k]);
        printf("\n");
    }
    return 0;
}