CodeChef submission 108888 (C++ 4.0.0-8) plaintext list. Status: AC, problem HX, contest OCT09. By braineater (Harpreet Singh), 2009-10-11 14:54:04.
#include <cstdio>
#include <vector>
#include <cmath>
#include <cassert>
#include <algorithm>
using namespace std;
 
int N;
float Q[2000][2000];
int A[2000][2000];
 
float M[2000][2000][6];
 
float escore(int i1, int j1, int i2, int j2)
{
  if(i2>=0 and j2>=0 and i2<N and j2<N)
    return Q[i1][j1]*Q[i2][j2];
  else 
    return 0;
}
 
void precalcM()
{
  for(int i=0; i<N; i++){
    for(int j=0; j<N; j++){
      M[i][j][0] = escore(i,j,i+1,j);
      M[i][j][1] = escore(i,j,i,j+1);
      M[i][j][2] = escore(i,j,i-1,j);
      M[i][j][3] = escore(i,j,i,j-1);
      
      int j1;
      if(i%2) j1=j+1; else j1=j-1;
      
      M[i][j][4] = escore(i,j,i+1,j1);
      M[i][j][5] = escore(i,j,i-1,j1);
    }
  }
}
 
float Vscore()  // score of vertical edges irrespective of polarity
{
  float ret=0;
  for(int i=0; i<N; i++) 
    for(int j=0; j<N; j++)
      ret += M[i][j][0]+M[i][j][2];
  return ret;
}
 
float Hscore()  // score of vertical edges irrespective of polarity
{
  float ret=0;
  for(int i=0; i<N; i++) 
    for(int j=0; j<N; j++)
      ret += M[i][j][1]+M[i][j][3];
  return ret;
}
 
float Dscore()  // score of vertical edges irrespective of polarity
{
  float ret=0;
  for(int i=0; i<N; i++) 
    for(int j=0; j<N; j++)
      ret += M[i][j][4]+M[i][j][5];
  return ret;
}
 
float vscore(int i, int j)
{
  float ret=0;
  int a = A[i][j];
  if(i+1<N and A[i+1][j] == a) ret += M[i][j][0];
  if(j+1<N and A[i][j+1] == a) ret += M[i][j][1];
  if(i>0 and A[i-1][j] == a) ret += M[i][j][2];
  if(j>0 and A[i][j-1] == a) ret += M[i][j][3];
  
  int j1;
  if(i%2) j1=j+1; else j1=j-1;
  
  if(j1>=0 and j1<N){
    if(i+1<N and A[i+1][j1] == a) ret += M[i][j][4];
    if(i>0 and A[i-1][j1] == a) ret += M[i][j][5];
  }
  //printf("vscore %d %d = %f\n", i, j, ret);
  return ret;
}
 
float getscore()
{
  float score = 0;
  for(int i=0; i<N; i++)
    for(int j=0; j<N; j++)
      score += vscore(i,j);
  score/=2;
  return score;
}
 
void myscanf(char **s, float &v)
{
  v=0;
  while(!(**s>='0' and **s<='9')){ (*s)++; }
  while(**s>='0' and **s<='9'){
    v = v*10 + **s-'0';
    (*s)++;
  }
  if(**s=='.'){
    float m=1.0/10;
    (*s)++; 
    while(**s>='0' and **s<='9'){
      v += m*(**s-'0');
      (*s)++; m/=10; 
    }
  }
}
 
char outbuf[2010*2000*2];
void prn()
{
  int c=0;
  for(int i=0; i<N; i++){
    for(int j=0; j<N; j++){
      if(j) outbuf[c++]=' ';
      outbuf[c++] = '0'+A[i][j];
    }
    outbuf[c++]='\n';
  }
  outbuf[c]='\0';
  fwrite(outbuf, 1, c, stdout);
}
 
void relax(int i, int j)
{
  float s1 = vscore(i,j);
  A[i][j] ^= 1;
  float s2 = vscore(i,j);
  if(s1<s2) 
    A[i][j] ^= 1;
}
 
int main()
{
  scanf("%d\n", &N);
  const int IS = 35000000;
  char *str = (char *) malloc(IS+5);
  fread(str, 1, IS, stdin);
  assert(feof(stdin));
	
  char *p=str;
  int n=0;
  for(int i=0; i<N; i++)
    for(int j=0; j<N; j++){
      myscanf(&p, Q[i][j]);
      A[i][j]=(i+j)%2;
    }
 
  assert(p-str<=IS);
  free(str);
  
  precalcM();
 
  //float vs = Vscore(), hs=Hscore(), ds=Dscore();
  //fprintf(stderr, "vs=%f hs=%f ds=%f\n", vs, hs, ds);
  //if(ds<=hs and ds<=vs) for(int i=0; i<N; i++) for(int j=0; j<N; j++) A[i][j]=(i+j)%2;
  //else if(hs<=vs) for(int i=0; i<N; i++) for(int j=0; j<N; j++) A[i][j]=i%2;
  //else for(int i=0; i<N; i++) for(int j=0; j<N; j++) A[i][j]=j%2;
 
  //hex
 
  for(int i=0; i<N; i++){
    for(int j=0; j<N; j++){
      int j3 = (j+3-i%2)%3;
      if(j3==0) A[i][j] = 1;
      else if(j3==2) A[i][j] = 0;
    }
  }
  for(int i=0; i<N; i++){
    for(int j=0; j<N; j++){
      int j3 = (j+3-i%2)%3;
      if(j3==1){
	float s1 = vscore(i,j);
	A[i][j] ^= 1;
	float s2 = vscore(i,j);
	if(s1<s2) 
	  A[i][j] ^= 1;
      }
    }
  }
 
  /*
  //row-wise
  int parity=0;
  for(int i=1; i<N; i++){
    float diff=0;
    for(int j=0; j<N; j++){
      diff += M[i][j][2] - M[i][j][5];
      //printf("  diff+=%f-%f\n", M[i][j][2], M[i][j][5]);
    }
    //printf("i=%d diff=%f\n", i, diff);
    if(diff<0) parity++;
    for(int j=0; j<N; j++) A[i][j] = (i+j+parity)%2;
  }  
  */
 
  
  for(int k=0; k<3; k++){
    //prn(); printf("score = %f\n", getscore());
    for(int i=0; i<N; i++){
      for(int j=0; j<N; j++){
	//if(k<=1 and Q[i][j]<0.3) continue;
	float s1 = vscore(i,j);
	A[i][j] ^= 1;
	float s2 = vscore(i,j);
	if(s1<s2) 
	  A[i][j] ^= 1;
      }
    }
  }
  
  //printf("asdf\n");
  prn();  
  //float score = getscore();
  //fprintf(stderr, "N=%d score=%f score1=%f\n", N, score, 440*score/(N*N));
  return 0;
}