Submission #634881

#	Time	Username	Problem	Language	Result	Execution time	Memory
634881		PoonYaPat	Gondola (IOI14_gondola)	C++14	65 / 100	19 ms	2644 KiB

gondola

#include "gondola.h"
 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int mod=1000000009;
bool have[250001];
int head[250001];
 
 
int valid(int n, int s[]) {
    bool ans=true;
    int sc=0;
 
    for (int i=0; i<n; ++i) {
        if (have[s[i]]) return 0;
        have[s[i]]=true;
        if (s[i]<=n && sc==0) sc=i;
    }
  
  	if (sc==0) return 1;
 
    int val=s[sc];
    for (int i=sc+1; i<n; ++i) {
        ++val;
        if (val>n) val-=n;
        if (s[i]<=n && s[i]!=val) {
            ans=false;
            break;
        }
    }
 
    return ans;
}
 
//----------------------
 
int replacement(int n, int s[], int ans[]) {
    int mmax=0,hm,sc=0;
    bool fix=false;
    for (int i=0; i<n; ++i) {
        mmax=max(mmax,s[i]);
        if (s[i]<=n) {
            fix=true;
            if (sc==0) sc=i;
        }
    }
 
    if (!fix) {
        for (int i=0; i<n; ++i) {
            head[s[i]]=i+1;
        }
    } else {
        int val=s[sc];
        for (int i=sc; i<n; ++i) {
            head[s[i]]=val++;
            if (val>n) val-=n;
        }
      	for (int i=0; i<sc; ++i) {
          	head[s[i]]=val++;
          	if (val>n) val-=n;
        }
    }
    hm=head[mmax];
 
    int idx=0;
    for (int i=n+1; i<mmax; ++i) {
        if (!head[i]) {
            ans[idx++]=hm;
            hm=i;
        } else {
            ans[idx++]=head[i];
        }
    }
    ans[idx]=hm;
 
    return mmax-n;
}
 
//----------------------
 
int countReplacement(int n, int s[]) {
    if (!valid(n,s)) return 0;
 
    ll ans=1;
    bool rot=false;
 
    int cnt=n,mmax=0;
    for (int i=0; i<n; ++i) {
        have[s[i]]=true;
        if (s[i]<=n) --cnt;
        mmax=max(mmax,s[i]);
    }
 
    if (cnt==n) rot=true;
 
    for (int i=n+1; i<=mmax; ++i) {
        if (have[i]) --cnt;
        else if (cnt) ans=(ans*cnt)%mod;
    }
 
    if (rot) {
        for (int i=1; i<=n; ++i) ans=(ans*i)%mod;
    }
 
    return ans%mod;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 20 / 20
• Subtask 7: 5 / 5
• Subtask 8: 15 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10