Submission #10186871


Source Code Expand

/// https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_d
#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rng(1);
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0);
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1<<(i-1)))
#define gg exit(0);

const int N=100010;

int n;
int cnt[N],a[N],b[N],dd[N],to[N];
priority_queue<ii> q;

int root(int i){
    return to[i]==i ? i : to[i]=root(to[i]);
}

main(){
    #define task "arrangement"
    //freopen(task".inp","r",stdin);
    //freopen(task".out","w",stdout);

    if((n=in)==2) return cout<<-1,0;
    forinc(i,1,n) cnt[a[i]=in]++;
    forinc(i,1,n){
        q.push({(n==100000) ? cnt[a[i]] :  cnt[i],i});
        to[i]=i;
    } to[n+1]=n+1;

    forinc(i,1,n-min(n,5)){
        while(q.size() && (dd[q.top().se] || q.top().fi!=cnt[q.top().se])) q.pop();
        if(q.size() && q.top().fi==n-i){
            b[i]=q.top().se;
            to[q.top().se]=q.top().se+1;
            cnt[a[b[i]]]--;
            q.push({cnt[a[b[i]]],a[b[i]]});
            dd[b[i]]=1;
            q.pop();
        } else{
            for(int j=root(1);j<=n;j=root(j+1))
                if(j!=a[b[i-1]]){
                    dd[b[i]=j]=1;
                    to[j]=j+1;
                    break;
                }
        }
    }

    vector<int> lf;
    forinc(i,1,n) if(to[i]==i) lf.pb(i);
    int b4=b[n-min(n,5)];
    do{
        if(a[b4]==lf[0]) continue;
        int i=0; while(i<lf.size()-1 && a[lf[i]]!=lf[i+1]) i++;
        if(i==lf.size()-1){
            forinc(j,1,n-min(n,5)) cout<<b[j]<<" ";
            forv(j,lf) cout<<j<<" ";
            gg
        }
    } while(next_permutation(all(lf)));
}

Submission Info

Submission Time
Task D - Arrangement
User unx
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2344 Byte
Status WA
Exec Time 29 ms
Memory 3700 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 800
Status
AC × 3
AC × 39
WA × 11
Set Name Test Cases
Sample sample_01, sample_02, sample_03
All hand2_01, hand2_02, hand2_03, hand2_04, hand_01, hand_02, hand_03, hand_04, handmaid_01, max_01, max_02, max_03, max_04, max_05, random_01, random_02, random_03, random_04, random_05, random_06, random_07, random_08, random_09, random_10, random_11, random_12, random_13, random_14, random_15, sample_01, sample_02, sample_03, small_01, small_02, small_03, small_04, small_05, special2_01, special2_02, special2_03, special2_04, special2_05, special2_06, special2_07, special2_08, special2_09, special2_10, special_01, special_02, special_03
Case Name Status Exec Time Memory
hand2_01 AC 1 ms 256 KB
hand2_02 AC 1 ms 256 KB
hand2_03 AC 20 ms 3316 KB
hand2_04 WA 20 ms 2676 KB
hand_01 AC 1 ms 256 KB
hand_02 AC 1 ms 256 KB
hand_03 AC 20 ms 3700 KB
hand_04 AC 28 ms 3700 KB
handmaid_01 AC 1 ms 256 KB
max_01 AC 28 ms 3700 KB
max_02 AC 29 ms 3700 KB
max_03 AC 29 ms 3572 KB
max_04 AC 29 ms 3700 KB
max_05 AC 29 ms 3316 KB
random_01 AC 1 ms 256 KB
random_02 AC 1 ms 256 KB
random_03 AC 1 ms 256 KB
random_04 AC 1 ms 256 KB
random_05 AC 1 ms 256 KB
random_06 AC 1 ms 256 KB
random_07 AC 1 ms 256 KB
random_08 AC 1 ms 256 KB
random_09 AC 1 ms 256 KB
random_10 AC 1 ms 256 KB
random_11 AC 1 ms 256 KB
random_12 AC 1 ms 256 KB
random_13 AC 1 ms 256 KB
random_14 AC 1 ms 256 KB
random_15 AC 1 ms 256 KB
sample_01 AC 1 ms 256 KB
sample_02 AC 1 ms 256 KB
sample_03 AC 1 ms 256 KB
small_01 AC 1 ms 256 KB
small_02 AC 1 ms 256 KB
small_03 AC 1 ms 256 KB
small_04 AC 1 ms 256 KB
small_05 AC 1 ms 256 KB
special2_01 WA 20 ms 2676 KB
special2_02 WA 20 ms 2676 KB
special2_03 WA 20 ms 2676 KB
special2_04 WA 20 ms 2676 KB
special2_05 WA 20 ms 2676 KB
special2_06 WA 20 ms 3060 KB
special2_07 WA 21 ms 3060 KB
special2_08 WA 20 ms 3060 KB
special2_09 WA 21 ms 3060 KB
special2_10 WA 20 ms 3060 KB
special_01 AC 1 ms 256 KB
special_02 AC 2 ms 512 KB
special_03 AC 29 ms 3700 KB