Submission #10183712

---

Source Code Expand

#include<bits/stdc++.h>
#define int ll
//{ PXH612
using namespace std;
#define ll long long
#define pp pair<int,int>
#define x first
#define y second

#define in ({ll x=0;int o=0,c=char();for(;!isdigit(c);c=getchar()) o=c=='-';for(;isdigit(c);c=getchar()) x=x*10+c-'0';o?-x:x;})
#define inchar ({char c=getchar();while(c==' '||c=='\n') c=getchar();c;})

auto min(auto a,auto b){return a<b?a:b;}
auto max(auto a,auto b){return a>b?a:b;}
bool Min(auto &a,auto b) {if(a>b) {a=b;return true;}return false;}
bool Max(auto &a,auto b) {if(a<b) {a=b;return true;}return false;}

#define FOR(i,a,b) for(int i=a,_=b;i<=_;i++)
#define ROF(i,a,b) for(int i=b,_=a;_<=i;i--)
#define RR(x,a,b) {cout<<#x<<": ";FOR(__,a,b) cout<<x[__]<<" ";cout<<"\n";}
#define rr(x) " "<<#x<<'='<<x<<" "

#define bit(x,i) ((x>>(i-1))&1ll)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1ll<<(i-1)))
#define bitnum(x) __builtin_popcountll(x)
#define mu(x) (1ll<<x)

#define VEC(i,a) for(auto&i:a)
#define pb push_back
#define vn(a) (int)a.size()-1

#define false(x) if(!(x))
#define midd(a,b) (a+(b-(a))/2)
#define open(x) freopen(x,"r",stdin)
#define shut(x) freopen(x,"w",stdout)
//}//////////////////////////////////////////

const int N=1e5+5;
int n;
int a[N],cnt[N];
int d[N],ans[N];

priority_queue<int,vector<int>,greater<int>> h;
priority_queue<pp> hc;

void CHOOSE(int i,int x)
{
    ans[i]=x;
    cnt[a[x]]--;
    d[x]=1;
}
main()
{
   // open("arrange.inp");
    n=in;int TK=min(n,10);
    FOR(i,1,n) a[i]=in;
    FOR(i,1,n) cnt[a[i]]++;

    FOR(i,1,n) h.push(i);
    FOR(i,1,n) hc.push({cnt[i],i});
    FOR(id,1,n-TK)
    {
        while(hc.size())
        {
            int x=hc.top().y;
            if(hc.top().x != cnt[x])
            {
                hc.pop();
                hc.push({cnt[x],x});
            }
            else if(d[x]==1) hc.pop();
            else break;

        }
        while(h.size()&&d[h.top()]==1) h.pop();

        if(hc.size()&&hc.top().x==n-id) CHOOSE(id,hc.top().y);
        else
        {
            int x=h.top();h.pop();
            int y=h.top();h.pop();
            if(a[ans[id-1]]==x) CHOOSE(id,y),h.push(x);
            else CHOOSE(id,x),h.push(y);
        }
    }
    vector<int> v;
    FOR(i,1,n) if(d[i]==0) v.pb(i);
    sort(v.begin(),v.end());

    FOR(i,1,n-TK) cout<<ans[i]<<" ";
    do
    {
        int ok=1;
        if(a[ans[n-TK]]==v.front()) ok=0;
        FOR(i,1,vn(v)) if(a[v[i-1]]==v[i]) ok=0;
        if(ok==0) continue;
        //FOR(i,1,vn(v)) cout<<rr(v[i-1]) rr(a[v[i-1]]) rr(v[i]) "\n";

        VEC(i,v) cout<<i<<" ";exit(0);
    }
    while(next_permutation(v.begin(),v.end()));
    cout<<-1;
}

Submission Info

Judge Result