90pts,WA最后一个点
查看原帖
90pts,WA最后一个点
252549
Iwara楼主2024/8/7 11:09

RT

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll MAXN=1e6+5;
ll k,n,p,q;
ll col[MAXN];
ll num[MAXN],nxt[MAXN];
ll cnt;
void insert(ll pos,ll X){
    cnt++;
    num[cnt]=X;
    nxt[cnt]=nxt[pos];
    nxt[pos]=cnt;
    return;
}
void solve(ll now_col){
    ll pos=1,nxt_pos=0,lst_pos=0;
    while(num[pos]){
        nxt_pos=nxt[pos];
        if(num[pos]==num[nxt_pos]&&col[now_col])insert(pos,now_col),col[now_col]--;
        lst_pos=pos;
        pos=nxt_pos;
    }
    pos=1,nxt_pos=0,lst_pos=0;
    while(num[pos]){
        nxt_pos=nxt[pos];
        if(num[pos]!=now_col&&num[nxt_pos]!=now_col&&col[now_col])insert(pos,now_col),col[now_col]--;
        lst_pos=pos;
        pos=nxt_pos;
    }
    while(col[now_col])insert(lst_pos,now_col),col[now_col]--;
    return;
}
inline void rd(ll &x){
	char ch;x=0;
	while(!isdigit(ch=getchar()));
	for(x=ch^'0';isdigit(ch=getchar());x=x*10+(ch^'0'));
}
inline void print(int x){
	if(x/10) print(x/10);
	putchar(x%10+'0');
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    rd(k),rd(p),rd(q);
    for(int i=1;i<=k;i++)rd(col[i]);
    if(k==1){
        if(col[1]==1)cout<<1;
        else if(col[1]==2)cout<<"1 1";
        else cout<<0;
        return 0;
    }
    
    if(p!=q){
        for(int i=1;i<=col[p];i++)num[i]=p,nxt[i]=i+1;
        nxt[col[p]]=1e6+1;
        cnt=col[p];
        
        for(int i=1;i<=k;i++){
            if(i==p||i==q)continue;
            solve(i);
        }
        col[q]--;
        solve(q);
        ll pos=1,lst=0;
        bool fl=0;
        while(num[pos]){
            if(num[pos]==num[nxt[pos]]){
                fl=1;
                break;
            }
            lst=num[pos],pos=nxt[pos];
        }
        if(lst==q)cout<<0;
        else if(fl)cout<<0;
        else{
            pos=1;
            while(num[pos]){
                print(num[pos]),putchar(' ');
                pos=nxt[pos];
            }
            print(q);
        }
    }
    else{
        if(col[p]==1){
            cout<<0;
            return 0;
        }
        for(int j=1;j<=k;j++)if(j!=p){
            for(int i=1;i<=col[j];i++)num[i]=j,nxt[i]=i+1;
            nxt[col[j]]=1e6+1;
            cnt=col[j];
            q=j;
            break;
        }
        for(int i=1;i<=k;i++){
            if(i==p||i==q)continue;
            solve(i);
        }
        col[p]-=2;
        solve(p);
        ll pos=1,lst=0;
        bool fl=0;
        while(num[pos]){
            if(num[pos]==num[nxt[pos]]){
                fl=1;
                break;
            }
            lst=num[pos],pos=nxt[pos];
        }
        if(lst==p||fl)cout<<0;
        else{
            print(p),putchar(' ');
            pos=1;
            while(num[pos]){
                print(num[pos]),putchar(' ');
                pos=nxt[pos];
            }
            print(p);
        }   
    }
    return 0;
}
2024/8/7 11:09
加载中...