Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

帮忙看看为什么WA呢 内有判断方法

Posted by ACM_henry at 2008-10-09 20:18:43 on Problem 2893
//a. 若两格局中0的距离为偶数,两者的逆序数的奇偶性相同。
//b. 若两格局中0的距离为奇数,两者的逆序数的奇偶性相异。
#include <iostream>
using namespace std;
int p[1000][1000];
int nixu;

int cn;
int a[1000000];
int c[1000000];
void MergeSort(int l,int r)
{
     int mid,i,j,tmp;
     if (r>l+1)
     {
         mid = (l+r)/2;
         MergeSort(l,mid);
         MergeSort(mid,r);
         tmp = l;
         for (i=l,j=mid;i<mid&&j<r;)
         {
             if (a[i]>a[j])
             {
                 c[tmp++] = a[j++];
                 cn+=mid-i;
             }
             else  c[tmp++] = a[i++];
         }
         if (j<r) for (;j<r;++j) c[tmp++] = a[j];
         else  for (;i<mid;++i)  c[tmp++] = a[i];
         
         for (i=l;i<r;++i)
             a[i] = c[i];
     }
}
int main()
{
	int m,n;
	int i,j;
	int nowx,nowy;
	int d;
	int num;
	while(cin>>m>>n&&m&&n)
	{
		num=0;
		cn=0;
		for(i=1;i<=m;i++)
		{
			for(j=1;j<=n;j++)
			{
				scanf("%d",&p[i][j]);
				a[num++]=p[i][j];
				if(p[i][j]==0)
				{
					nowx=i;
					nowy=j;
				}
			}
		}
		nixu=m*n-1;
		d=m-nowx+n-nowy;
		MergeSort(0,num);
		//cout<<cn<<"   "<<nixu<<"   "<<d<<endl;
		if(d%2==0&&(nixu%2==0&&cn%2==0||nixu%2==1&&cn%2==1))
		{
			cout<<"YES"<<endl;
		}
		else if(d%2==1&&(nixu%2==0&&cn%2==1||nixu%2==0&&cn%2==1)) 
		{
			cout<<"YES"<<endl;
		}
		else cout<<"NO"<<endl;
	}
	return 0;
}
 


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator