Submission #1136057

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136057		HasanV11010238	Gondola (IOI14_gondola)	C++20	100 / 100	45 ms	5188 KiB

gondola

#include <bits/stdc++.h>
#include "gondola.h"
#define ll long long
#define mod 1000000009
using namespace std;
ll binpow(ll a, ll b){
    ll res = 1;
    while (b != 0){
        if (b % 2 == 0){
            b /= 2;
            a *= a;
            a %= mod;
        }
        else{
            b--;
            res *= a;
            res %= mod;
        }
    }
    return res;
}
int valid(int n, int inputSeq[])
{
    map<int, int> ma;
    int mind = -1;
    for (int i = 0; i < n; i++){
        if (inputSeq[i] <= n){
            if (mind == -1 || inputSeq[i] < inputSeq[mind]){
                mind = i;
            }
        }
        if (ma[inputSeq[i]] > 0) return 0;
        ma[inputSeq[i]]++;
    }
    if (mind == -1) return 1;
    int va = inputSeq[mind];
    for (int i = 0; i < va - 1; i++){
        mind--;
        if (mind < 0) mind = n - 1;
    }
    for (int i = 0; i < n; i++){
        int no = (i + mind) % n;
        if (inputSeq[no] <= n && inputSeq[no] != i + 1){
            return 0;
        }
    }
    return 1;
}

int replacement(int n, int go[], int rep[])
{
    if (valid(n, go) == 0) return 0;
    int mind = -1;
    for (int i = 0; i < n; i++){
        if (go[i] <= n){
            if (mind == -1 || go[i] < go[mind]){
                mind = i;
            }
        }
    }
    if (mind == -1){
        mind = 0;
    }
    else{
        int va = go[mind];
        for (int i = 0; i < va - 1; i++){
            mind--;
            if (mind < 0) mind = n - 1;
        }
    }
    vector<vector<int>> v; 
    for (int i = 0; i < n; i++){
        int no = (i + mind) % n;
        if (go[no] > n){
            v.push_back({go[no], i + 1});
        }
    }
    sort(v.begin(), v.end());
    int ind = 0, no = n + 1, cnt = 0;
    for (auto el : v){
        while (el[1] != el[0]){
            rep[ind] = el[1];
            el[1] = no;
            no++;
            ind++;
        }
    }
    return ind;
}

int countReplacement(int n, int inp[])
{
    if (valid(n, inp) == 0) return 0;
    int mind = -1;
    for (int i = 0; i < n; i++){
        if (inp[i] <= n){
            if (mind == -1 || inp[i] < inp[mind]){
                mind = i;
            }
        }
    }
    ll ans = 1;
    if (mind == -1){
        ans = n;
        mind = 0;
    }
    else{
        int va = inp[mind];
        for (int i = 0; i < va - 1; i++){
            mind--;
            if (mind < 0) mind = n - 1;
        }
    }
    vector<ll> v; 
    for (int i = 0; i < n; i++){
        int no = (i + mind) % n;
        if (inp[no] > n){
            v.push_back(inp[no]);
        }
    }
    sort(v.begin(), v.end());
    ll la = n, le = 1LL * v.size();
    for (auto el : v){
        ll hm = el - la - 1;
        ans *= binpow(le, hm);
        le--;
        ans %= mod;
        la = el;
    }
    return ans;
}

• 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: 10 / 10