Cod sursă (job #143339)

#include <stdio.h>
#include <algorithm>
#include <assert.h>
#define NMax 145
#define LMax (NMax * NMax)
using namespace std;

const int d[4][2] = {
  {-1, 0},
  {0, 1},
  {1, 0},
  {0, -1}
};

int N, L, free_elem;
int Mat[LMax][LMax], p[LMax], rez[LMax];
int sol[NMax][NMax];

inline int poz( int x, int y ) {
  return ( x - 1 ) * N + y;
}

void gauss() {

  int pivot, i, j;

  for ( i = 1; i <= L; ++ i) p[i] = i;

  for ( pivot = 1; pivot <= L; ++ pivot ) {
   
    // change line if needed
    if ( Mat[pivot][pivot] == 0 ) {
      for ( i = pivot + 1; i <= L && Mat[i][pivot] != 1; ++ i );
      if ( i > L ) continue;

      for ( j = pivot; j <= L + 1; ++ j )
        swap( Mat[i][j], Mat[pivot][j] );
      swap(p[i], p[pivot]);
    }

    for ( i = pivot + 1; i <= pivot + N && i <= L; 
                        ++ i ) if ( Mat[i][pivot] == 1 ) {
      for ( j = pivot; j <= pivot + 2 * N && j <= L; ++ j)
      Mat[i][j] ^= Mat[pivot][j];
      Mat[i][L + 1] ^= Mat[pivot][L + 1];
    }
  }

  for ( i = L; i > 0; -- i) {
    rez[i] = Mat[i][L + 1];
    free_elem += Mat[i][i] == 0;
    for ( j = i + 1; j <= L; ++ j) if ( Mat[i][j] )
      rez[i] ^= rez[j];
  }
}

int main() {

  int i, j, dir;
  freopen("in.txt", "r", stdin);
  assert( scanf("%d", &N) == 1);

  for ( i = 1; i <= N; ++ i)
    for ( j = 1; j <= N; ++ j) {
      Mat[ ++ L ][ poz(i,j) ] = 1;
      for ( dir = 0; dir < 4; ++ dir) {
        int nx = i + d[dir][0];
        int ny = j + d[dir][1];

        if ( 1 <= nx && nx <= N && 1 <= ny && ny <= N )
          Mat[ L ][ poz(nx, ny) ] = 1;
      }
    }

  for ( i = 1; i <= L; ++ i)
    Mat[i][L + 1] = 1;

  gauss();

  /*for ( i = 1; i <= L; ++ i, printf("\n"))
    for ( j = 1; j <= L + 1; ++ j)
      printf("%d ", Mat[i][j]);
  
  printf("\n");
  for ( i = 1; i <= L; ++ i)
    printf("%d ", p[i]);
  printf("\n");

  printf("\n");
  for ( i = 1; i <= L; ++ i)
    printf("%d ", rez[i]);
  printf("\n");

  printf("FREE: %d\n", free_elem);
  */

  for ( i = 1; i <= L; ++ i) if ( rez[i] ) 
    sol[ (i - 1) / N + 1 ][ (i - 1) % N + 1] = 1;

  freopen("out.txt", "w", stdout);
  for ( i = 1; i <= N; ++ i, printf("\n"))
    for ( j = 1; j <= N; ++ j)
      printf("%d ", sol[i][j]);
  fclose(stdout);
  return 0;
}