CodeChef submission 79963 (C++ 4.0.0-8) plaintext list. Status: TLE, problem NSUDOKU, contest AUGMINI. By pr0ton (Pratik Tandel), 2009-08-24 14:58:23.
 
#include<queue>
#include<fstream>
#include<cstdlib>
 
 
 
 
 
#define oo 					(int)13e7
#define sl(n) 					scanf("%lld",&n)
#define sf(n) 					scanf("%lf",&n)
#define fill(a,v) 				memset(a, v, sizeof a)
#define ull 					unsigned long long
#define ll 						long long
#define bitcount 			__builtin_popcount
#define all(x) 				x.begin(), x.end()
#define pb( z ) 				push_back( z )
#define gcd					__gcd
using namespace std;
 
const int mx = 901;
int a[mx][mx];
int n, k;
bool row[mx][mx], col[mx][mx];
int bxid[mx][mx];
bool box[mx][mx];
int n2, cnt[mx];//, cnt2[mx];
// put at x, y value d
inline void put( int x, int y,int d )
{
	a[x][y] = d;
	int b = bxid[ x ][ y ];
	box[ b ][ d ] = 1;
	row[ x ][ d ] = 1;
	col [ y ][ d ] = 1;
	--cnt[ d ]; 
	//cnt2[ d ]--;
}
 
 
/*
const int mxip = (int)4.5e6;
char ip[ mxip ];
int ipsz = 0;
*//*
const int mxop = (int)2.8e6;
char op[ mxop ];
int opsz = 0;*/
#define pchar(c) putchar_unlocked(c)//op[opsz++] = c
#define getcx() getchar_unlocked()
inline void s( int &n )
{
	n=0;
	int ch=getcx();
	while( ch < '0' || ch > '9' ) ch=getcx();
	
	while(  ch >= '0' && ch <= '9' )
		n = (n<<3)+(n<<1) + ch-'0', ch=getcx();
}
 
//fast output to buffer, and then print using fwrite
inline void writeNum( int x )
{
	int tmp;
	if( x >= 100 )
	{
		tmp = x / 100;
		pchar( '0' + tmp );
		x -= tmp * 100;
		tmp = x/10;
		pchar( '0' + tmp );
		x -= tmp * 10;
		pchar( '0' + x );
	}
	else if( x >= 10 )
	{
		tmp = x/10;
		pchar( '0' + tmp );
		x -= tmp * 10;
		pchar( '0' + x );
	}
	else
	{
		pchar( '0' + x );
	}
}
 
 
 
static unsigned int g_seed;
//init
inline void fast_srand( int seed )
{
	g_seed = seed;
}
//fast random generator between 0 and 32767
inline int fastrand()
{
	g_seed = (214013*g_seed+2531011);
	return (g_seed>>16)&0x7FFF;
}
int konst = 1;
int mod[ 32768 ]; //precomputed mod n2
int main()
{
	
	//fread( ip, mxip, 1, stdin );
	int start = clock(); //timer
	fast_srand(  clock() );
	s( n ); s( k );
	n2 = n*n;
	
	#ifdef ONLINE_JUDGE
	#else 
	printf("%d\n", n);
	#endif
	
	
	
	//assign box ids to each cell
	for(int i=1; i <= n2; i++)
	for(int j=1; j <= n2; j++)
		bxid[i][j] = n* ( (i-1)/n ) + (j-1)/n;
	//read input
	for(int i=0; i < k; i++)
	{
		int x, y, v;
		s(x); s(y); s(v);
		put( x, y, v );
	}
	
	for(int i=1; i < 32768; ++i)
	{
		mod[i] = mod[i-1] + 1 ;
		if( mod[i] == n2 )
			mod[i] = 0;
		mod[i-1]++;
	}
	mod[32767]++;
	const double delta = 2.5 + min( 0.31, ( 0.25 * n2 / 900 ) );
	int mtries = 5.25e8 / ( n2*n2 );
	int ch2 = 7.7e7 / ( n2*n2 );
	for(int i=1; i <= n2; i++)
	{
	for(int j=1; j <= n2; j++)
		if( a[i][j] == 0 )
		{
			int zx = mod[ fastrand() ] ;
			{
				int tries = mtries;
				char bcost = 3; int bbit = zx;
				while( tries--)
				{
					zx = mod[ fastrand() ] ;
					char ccost = 0;
					if( row[i][zx] ) ccost++;
					if( col[j][zx] ) ccost++;
					if( box[ bxid[i][j] ] [ zx ] ) ccost++;
					if( ccost < bcost )
					{
						bcost = ccost;
						bbit = zx;
						if( bcost == 0 ) break;
					}
					else if( bcost == ccost )
					{
						if( cnt[ bbit ] > cnt[ zx ] )
							bbit = zx;
					}
					
				}
				zx = bbit;
			}
			put( i, j, zx );
			
		} 
		int cur = clock();
		double secs = ( start - cur + 0.0 ) / CLOCKS_PER_SEC;
		if( secs > delta )
			mtries = ch2;
	}
	
	for(int i=1; i <= n2; i++)
	for(int j=1; j <= n2; j++)
	{
		writeNum( a[i][j] );
		//if( j  < n2 )
			pchar(  ' ' );
		//else
		//	pchar( '\n' );
	}
	//fwrite (op , 1 , opsz , stdout );
	
	return 0;
}