Submission #10183790


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({cnt[a[i]],i});
        to[i]=i;
    } to[n+1]=n+1;

    forinc(i,1,n){
        while(q.size() && dd[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;
            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;
                }
        }
    }
    forinc(i,1,n) cout<<b[i]<<" ";
}

Submission Info

Submission Time
Task D - Arrangement
User unx
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1825 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 × 1
WA × 2
AC × 3
WA × 47
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 WA 1 ms 256 KB
hand2_02 WA 1 ms 256 KB
hand2_03 WA 28 ms 3316 KB
hand2_04 WA 29 ms 3316 KB
hand_01 WA 1 ms 256 KB
hand_02 WA 1 ms 256 KB
hand_03 WA 27 ms 3700 KB
hand_04 WA 27 ms 3700 KB
handmaid_01 WA 1 ms 256 KB
max_01 WA 20 ms 3700 KB
max_02 WA 21 ms 3700 KB
max_03 WA 23 ms 3572 KB
max_04 WA 20 ms 3700 KB
max_05 WA 20 ms 3316 KB
random_01 WA 1 ms 256 KB
random_02 WA 1 ms 256 KB
random_03 WA 1 ms 256 KB
random_04 WA 1 ms 256 KB
random_05 WA 1 ms 256 KB
random_06 WA 1 ms 256 KB
random_07 WA 1 ms 256 KB
random_08 WA 1 ms 256 KB
random_09 AC 1 ms 256 KB
random_10 AC 1 ms 256 KB
random_11 WA 1 ms 256 KB
random_12 WA 1 ms 256 KB
random_13 WA 1 ms 256 KB
random_14 WA 1 ms 256 KB
random_15 WA 1 ms 256 KB
sample_01 WA 1 ms 256 KB
sample_02 AC 1 ms 256 KB
sample_03 WA 1 ms 256 KB
small_01 WA 1 ms 256 KB
small_02 WA 1 ms 256 KB
small_03 WA 1 ms 256 KB
small_04 WA 1 ms 256 KB
small_05 WA 1 ms 256 KB
special2_01 WA 28 ms 3316 KB
special2_02 WA 28 ms 3316 KB
special2_03 WA 28 ms 3316 KB
special2_04 WA 28 ms 3316 KB
special2_05 WA 28 ms 3316 KB
special2_06 WA 28 ms 3700 KB
special2_07 WA 28 ms 3700 KB
special2_08 WA 28 ms 3700 KB
special2_09 WA 28 ms 3700 KB
special2_10 WA 28 ms 3700 KB
special_01 WA 1 ms 256 KB
special_02 WA 2 ms 512 KB
special_03 WA 20 ms 3700 KB