C++(g++ 7.5.0) 解法, 执行用时: 207ms, 内存消耗: 1584K, 提交时间: 2023-07-24 11:15:03

#include<bits/stdc++.h>
using namespace std;
int N,a,T[300012];
inline void up(int x){for(int i=x;i<=N;i+=i&-i)++T[i];}
inline int query(int x)
{
    int res=0;
    for(int i=x;i;i-=i&-i) res+=T[i];
    return res;
}
inline int update()
{
    memset(T,0,sizeof(T));
	int cnt=0;
    for(int g=1;g<=N;++g)
    {
        scanf("%d",&a);
        if(!a) continue;
        cnt+=query(N)-query(a); up(a);
    }
    return cnt&1;
}
int main()
{
    for(;scanf("%d",&N)==1;)
    {
        N*=N;
        if(update()==update())
		cout<<"TAK"<<endl;
		else
		cout<<"NIE"<<endl;
    }
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 328ms, 内存消耗: 1244K, 提交时间: 2020-08-15 20:25:21

#include<cstdio>
#include<cstring>
using namespace std;
int t[250000],n;

inline void add(int x) {
	for (; x<=n; x+=x&-x) t[x]++;
}

inline int qry(int x) {
	int ret=0;
	for (; x; x-=x&-x) ret+=t[x];
	return ret;
}

inline bool calc() {
	memset(t,0,sizeof t);
	int cnt=0;
	for (int i=1,x; i<=n; i++) {
		scanf("%d",&x);
		if (x) cnt+=qry(n)-qry(x),add(x);
	}
	return cnt&1;
}

int main() {
	while(~scanf("%d",&n))
		n*=n,calc()==calc() ? puts("TAK"):puts("NIE");
}

C++(clang++11) 解法, 执行用时: 250ms, 内存消耗: 1272K, 提交时间: 2020-11-24 21:45:07

#include<bits/stdc++.h>
#define low(i) (i&(-i))
using namespace std;
const int nn=251124;
int n,num,ans,c[nn];
void work(){
	memset(c,0,sizeof c);
	for(int i=1;i<=n;i++){
		scanf("%d",&num);
		if(num){
			for(int i=num;i;i-=low(i))
				ans+=c[i];
			for(;num<n;num+=low(num))
				c[num]++;
		}
	}
}int main(){
	for(;scanf("%d",&n)!=EOF;ans=0){
		n*=n,work(),work();
		puts((ans&1)?"NIE":"TAK");
	}return 0;
}