题解

必要条件

两个并行栈的调度遵循：车辆按输入序依次到来，只能堆放在某个栈顶；可以在任意时刻从任何一个栈顶弹出，输出顺序必须是 $1..n$。如果存在 $i<j<k$ 使得 $a_k < a_i < a_j$，则 $a_i$ 和 $a_j$ 不可能被放在同一个栈内——因为 $a_j$ 必须比 $a_i$ 更晚弹出，但它又挡在 $a_i$ 的上方。类似地，在整个过程中我们会不断发现“这些车辆必须放在不同的栈”这一类约束。

构建冲突图

按输入顺序扫描，用若干配对堆维护“当前尚未确定栈别的车辆集合”。一旦以下任一条件满足，就能得到新的冲突边：

1. 当前车辆比某个集合中的最小值还大，说明它与该集合的代表无法放同一栈，需要把两个集合合并并连边；
2. 右侧尚未出现的最小值小于某集合的最小值，说明这个集合对后续车辆再也不会产生影响，可以直接丢弃。

这样构造出的图是一张简单图，其边集合恰好对应“必须分到不同栈”的车辆对。若图不可二分，则无解；否则把每个连通分量染成两种颜色，就得到车厢入栈方案（颜色即栈号）。

验证方案

颜色合法并不代表一定能成功排序——还需验证：按得到的栈号模拟整个过程，遇到车辆就压入对应栈，然后不断检查两个栈顶是否等于当前要输出的编号，是则弹出并让 cur++。若最终 cur = n+1，说明方案有效；否则输出 NIE。

复杂度

配对堆维护集合，合并与查询均摊 O(\log n)，建图阶段整体复杂度 $O(n \log n)`；随后做一次 DFS 染色和一次栈模拟，复杂度$O(n)$。因此可轻松处理$n \le 10^5$。

参考代码

#include<bits/stdc++.h>
//#pragma GCC optimize(2)
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_pbds;
//#define int long long
#define ll long long
#define ull unsigned ll
#define db double
#define ldb long db
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pbI push_back
#define inf 1e9
#define mdI int mid=(l+r)>>1
#define lowbit(x) ((x)&(-(x)))
#define ppc(x) __builtin_popcount(x)
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define vep(a,b,c) for(int a=b;a>=c;a--)
#define gint __int128
#define MOD 1000000007//998244353
#define MAXN 100010
int qread(){
	char o=getchar();int f=1,x=0;
	for(;!isdigit(o);o=getchar())if(o=='-')f*=-1;
	for(;isdigit(o);o=getchar())x=x*10+o-'0';
	return f*x;
}
ll qp(ll a,ll b,ll p=MOD){
    ll bs=a,rs=1;while(b){if(b&1)rs=rs*bs%p;bs=bs*bs%p;b>>=1;}return rs;
}
void exgcd(ll a,ll b,ll &x,ll &y){if(b==0){x=1,y=0;return;}exgcd(b,a%b,y,x);y-=(a/b)*x;}
ll inv(ll a,ll p=MOD){ll x,y;exgcd(a,p,x,y);return (x+p)%p;}
void chmi(int &x,int y){x=min(x,y);}
void chmx(int &x,int y){x=max(x,y);}
void chmd(signed &x,ll y){x=(x+y)%MOD;}
void chmd(ll &x,ll y,ll m=MOD){x=(x+y)%m;}
void chmd(gint &x,ll y,gint m=MOD){x=(x+y)%m;}
bool FLA;
int n,a[MAXN],suf[MAXN];
__gnu_pbds::priority_queue<pii,greater<pii> >pq[MAXN];//涓€鑸殑閰嶅鍫嗗嵆鍙紝鑰屼笖涓€鑸彧閫傚悎鐢ㄩ厤瀵瑰爢
vector<int>vec[MAXN];
int col[MAXN];
void dfs(int x,bool co){
    if(col[x]){if((col[x]-1)!=co){puts("NIE");exit(0);}return;}
    col[x]=co+1;
    for(auto v:vec[x]){dfs(v,!co);}
}
bool FLB;
signed main(){
    cerr<<((&FLB)-(&FLA))/1024.0/1024<<endl;
    cin>>n;
    rep(i,1,n)a[i]=qread();
    suf[n+1]=inf;
    vep(i,n,1)suf[i]=min(suf[i+1],a[i]);
    rep(i,1,n){
        pq[i].push(mp(a[i],i));
        while(pq[0].size()&&pq[0].top().fi<=suf[i+1]){
            int X=pq[0].top().se;
            pq[X].pop();pq[0].pop();
            if(pq[X].size())pq[0].push(mp(pq[X].top().fi,X));//pq[0]琚檺鍒舵€濈淮浜嗭紝鍙互鍜屽叾浣欑殑鎰忎箟涓嶅悓
        }
        while(pq[0].size()&&pq[0].top().fi<a[i]){
            int X=pq[0].top().se,wh=pq[X].top().se;
            pq[0].pop();pq[i].join(pq[X]);vec[i].pbI(wh);vec[wh].pbI(i);
        }
        pq[0].push(mp(pq[i].top().fi,i));
    }
    rep(i,1,n){if(!col[i])dfs(i,0);}//col0涓哄乏鏍堬紝杩欐牱浜﹀彲寰楀瓧鍏稿簭鏈€灏忚В
    int cur=1;
    stack<int>stk[2];
    rep(i,1,n){
        stk[col[i]-1].push(a[i]);
        while(1){
            if(stk[0].size()&&stk[0].top()==cur){
                cur++;stk[0].pop();continue;
            }
            if(stk[1].size()&&stk[1].top()==cur){
                cur++;stk[1].pop();continue;//杩欓噷婕忎簡涓€涓猚ontinue!
            }
            break;
        }
    }
    if(cur!=(n+1)){
        puts("NIE");return 0;
    }
    puts("TAK");
    rep(i,1,n)printf("%d ",col[i]);
}