AcWing 108. 奇数码问题
原题链接
中等
作者:
HUE_ACM
,
2021-12-16 17:02:28
,
所有人可见
,
阅读 255
const int N = 500 * 500 + 10;
int n, a[N], t[N];
int merge_sort(int l, int r) {
if(l >= r) return 0;
int mid = (l + r) >> 1;
int res = merge_sort(l, mid) + merge_sort(mid + 1, r);
int i = l, j = mid + 1, cnt = 0;
while(i <= mid && j <= r) {
if(a[i] <= a[j]) {
t[++cnt] = a[i++];
}
else {
t[++cnt] = a[j++];
res += mid - i + 1;
}
}
while(i <= mid) t[++cnt] = a[i++];
while(j <= r) t[++cnt] = a[j++];
for(int i = l, j = 1; i <= r; i++, j++) {
a[i] = t[j];
}
return res;
}AA
int main (void) {
while(cin >> n) {
for(int i = 1, j = 1; i <= n * n; i++) {
scanf("%d", &a[j]);
if(a[j]) j++;
}
int flag = merge_sort(1, n * n - 1) & 1;
for(int i = 1, j = 1; i <= n * n; i++) {
scanf("%d", &a[j]);
if(a[j]) j++;
}
flag ^= merge_sort(1, n * n - 1) & 1;
puts(flag ? "NIE" : "TAK");
}
return 0;
}