Submission #66376

#	Time	Username	Problem	Language	Result	Execution time	Memory
66376		someone_aa	Gondola (IOI14_gondola)	C++17	60 / 100	81 ms	10412 KiB

gondola

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

#define ll long long
using namespace std;
const int maxn = 250100;
const ll mod = 1000000009;
map<int, bool>exist;
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;
}

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

ll power(ll a, ll b) {
    if(b == 0) return 1LL;
    else if(b == 1) return 1LL * a % mod;
    else {
        if(b%2 == 0) {
            ll half = power(a, b/2) % mod;
            return (1LL*half * half)% mod;
        }
        else if(b%2==1) {
            return (power(a, b-1)) % mod;
        }
    }
}

int countReplacement(int n, int arr[]) {
    if(!valid(n, arr)) return 0;
    vector<ll>nums;
    for(int i=0;i<n;i++) {
        if(arr[i] > n) nums.push_back(arr[i]);
    }
    nums.push_back(n);
    sort(nums.begin(), nums.end());

    ll result = 1LL;
    for(int i=1;i<nums.size();i++) {
        ll diff = 1LL * nums[i] - nums[i-1] - 1;
        ll p = 1LL * int(nums.size()) - i;
        result *= 1LL*power(p, diff);
        result %= mod;
    }

    if(nums.size() > n) {
        result *= n;
        result %= mod;
    }
    return result;
}

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

Compilation message (stderr)

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:100:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<nums.size();i++) {
                 ~^~~~~~~~~~~~
gondola.cpp:107:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(nums.size() > n) {
        ~~~~~~~~~~~~^~~
gondola.cpp: In function 'long long int power(long long int, long long int)':
gondola.cpp:88:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• 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: 0 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10