2256592_ac_2389ms_8448k.cc

北大大牛代码 1240道题的原代码 超级权威

# include <stdio.h>

int m, n;
long p, pz[1001][1001];
long a[1000001], b[1000001];
int pi, pj;
long res;

void merge(long begin,long mid,long end)
{
	long i, j, k = 0;
	
	for(i = begin, j = mid+1; i <= mid && j <= end; k++)
	{
		if(a[i] <= a[j])
			b[k] = a[i++];
		else 
		{
			b[k] = a[j++];
			res += mid+1-i;
		}
	}
	for(; i <= mid; i++)
		b[k++] = a[i];
	for(; j <= end; j++)
		b[k++] = a[j];
	for(i = 0; i < k; i++)
		a[begin+i] = b[i];
}

void msort(long s, long t)
{
	if(s < t)
	{
		long m = (s+t)>>1;
		msort(s,m);
		msort(m+1,t);
		merge(s,m,t);
	}
}

void input()
{
	int i, j;

	while(scanf("%d%d",&m,&n)==2&&m&&n)
	{
		p = 0;res = 0;
		for(i = 0; i < m; i++)
			for(j = 0; j < n; j++)
			{
				scanf("%ld",&pz[i][j]);
				if(!pz[i][j])
					pi = i, pj = j;
			}
		while(pi!=m-1)
		{
			pi++;
			pz[pi-1][pj] = pz[pi][pj];
			pz[pi][pj] = 0;
		}
		while(pj!=n-1)
		{
			pj++;
			pz[pi][pj-1] = pz[pi][pj];
			pz[pi][pj] = 0;
		}
		for(i = 0; i < m; i++)
			for(j = 0; j < n; j++)
				if(pz[i][j])
					a[p++] = pz[i][j];
		msort(0,p-1);
		if(res%2)
			printf("NO\n");
		else
			printf("YES\n");
	}
}

int main()
{
	input();
	return 1;
}