2893.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Problem Id:2893  User Id:fzk 
Memory:8452K  Time:1375MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>
#include <memory.h>

int a[1000][1000];
int num[1000100], count;
int temp[1000100];

void merge( int l, int r ) {
	int c =(r+l)/2, j, t1, t2;
	if( r <= l+1 )
		return;
		
	merge( l, c );
	merge( c, r );
	
	memcpy( temp+l, num+l, sizeof(int)*(r-l) );
	
	t1 = l, t2 = c;
	for( j=l; j<r; j++ ) {
		if( t1 < c && ( t2 >= r || temp[t1] < temp[t2] ) )
			num[j] = temp[t1++];
		else {
			num[j] = temp[t2++];
			count += c-t1;
			count %= 2;
		}
	}

}

int n, m;

int main( ) {
	int i, j, h;
	while( 1 ) {
		scanf( "%d%d", &n, &m );
		if( n == 0 || m == 0 )
			break;

		for( i=0; i<n; i++ )
		for( j=0; j<m; j++ )
			scanf( "%d", &a[i][j] );
		
		h = 0;
		for( i=0; i<n; i++ )
		for( j=0; j<m; j++ )
			if( i%2==0 ) {
				if( a[i][j] != 0 )
					num[h++] = a[i][j];
			}
			else if( a[i][m-1-j] != 0 )
				num[h++] = a[i][m-1-j];

		count = 0;
		merge( 0, h );

		if( (count)%2 != (m-1)*m/2%2*(n/2)%2 )
			printf( "NO\n" );
		else
			printf( "YES\n" );
	}
	return 0;
}