Submission #66369

#	Time	Username	Problem	Language	Result	Execution time	Memory
66369		someone_aa	Gondola (IOI14_gondola)	C++17	90 / 100	42 ms	11576 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>

#define ll long long
using namespace std;
const int maxn = 250100;
const ll mod = 1000000009;
bool exist[maxn];
int fin_val[maxn];
ll cnt[maxn];

int valid(int n, int arr[]) {
    bool check = true;

    for(int i=1;i<n;i++) {
        if(arr[i] > n) continue;
        else if(arr[i] == 1) {
            if(arr[i-1] < n)
                check = false;
        }
        else {
            if(arr[i-1] <= n && arr[i-1] != arr[i] - 1) check = false;
        }
    }

    sort(arr, arr+n);
    for(int i=1;i<n;i++) {
        if(arr[i] == arr[i-1]) check = false;
    }
    if(check) return 1;
    else return 0;
}

//----------------------

int replacement(int n, int arr[], int replacementSeq[]) {
    int maxm = 0;
    int found_i = 0, st_val = 1;
    for(int i=0;i<n;i++) {
        exist[arr[i]] = true;
        if(arr[i] <= n) {
            found_i = i;
            st_val = arr[i];
        }
        maxm = max(maxm, arr[i]);
    }
    exist[n] = true;
    int l = maxm - n;


    for(int i=found_i;i<n;i++) {
        fin_val[i] = st_val;
        st_val++;
        if(st_val == n + 1) st_val = 1;
    }

    for(int i=0;i<found_i;i++) {
        fin_val[i] = st_val;
        st_val++;
        if(st_val == n + 1) st_val = 1;
    }

    for(int i=0;i<n;i++) {
        while(!exist[arr[i]-1] && arr[i] > n) {
            replacementSeq[arr[i]-n-1] = arr[i] - 1;
            arr[i]--;
        }
        if(arr[i] > n) replacementSeq[arr[i]-n-1] = fin_val[i];
    }

    return l;
}

//----------------------

int countReplacement(int n, int arr[]) {
    if(!valid(n, arr)) return 0;

    int minv = INT_MAX, maxv = 0;
    for(int i=0;i<n;i++) {
        minv = min(minv, arr[i]);
        maxv = max(maxv, arr[i]);
        exist[arr[i]] = true;
    }

    ll result = 1LL;
    for(int i=maxv;i>=n+1;i--) {
        cnt[i] = cnt[i+1];
        if(exist[i]) cnt[i]++;
    }
    for(int i=n+1;i<=maxv;i++) {
        if(!exist[i]) {
            result *= cnt[i];
            result %= mod;
        }
    }
    if(minv > n) {
        result *= n;
        result %= mod;
    }
    return result;
}

/*int main() {
    int arr[] = {2, 3, 4, 12, 6, 7, 1};
    int arr2[1];
    cout<<countReplacement(7, arr);
}*/

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