tjut 3600

#include<stdio.h> #define SIZE_N 90010 int ary[2][SIZE_N]; int sum,len; void reverseNum(int l,int h,int idx) { int i,j,k; int mid,idxt; idxt = 1 - idx; if(l == h) { ary[1][l] = ary[0][l]; return ; } mid = (l + h) / 2; reverseNum(l, mid, idxt); reverseNum(mid+1, h, idxt); for(i = j = l,k = mid+1;i <= mid && k <= h;) { if(ary[idx][i] < ary[idx][k]) { ary[idxt][j++] = ary[idx][i]; sum += k - mid - 1; i ++; } else { ary[idxt][j++] = ary[idx][k]; k ++; } } for(i;i <= mid;i ++) { ary[idxt][j++] = ary[idx][i]; sum += h - mid; } for(k;k <= h;k ++) { ary[idxt][j++] = ary[idx][k]; } } int main() { int n; int i; while(scanf("%d",&n),n != 0) { len = n * n; for(i = 0;i < len;i ++) { scanf("%d",&ary[0][i]); if(ary[0][i] == 0) { if(!(n & 1)) { sum = (n - i / n - 1); } else { sum = 0; } i --; len --; } } if(n == 1) { puts("YES"); continue; } reverseNum(0, len-1, 0); if(sum & 1) { puts("NO"); } else { puts("YES"); } } return 0; }