Submission #1229416

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229416		LucaIlie	Gondola (IOI14_gondola)	C++20	75 / 100	28 ms	4028 KiB

gondola

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

using namespace std;

const int INF = 1e9 + 1;
const int MOD = 1e9 + 9;
const int MAX_N = 1e5;

int lgput(int a, int n) {
    if (n == 0)
        return 1;

    int p = lgput(a, n / 2);
    p = (long long)p * p % MOD;
    if (n % 2 == 1)
        p = (long long)p * a % MOD;

    return p;
}

map<int, int> frecv;

int valid(int n, int inputSeq[]) {
    int pos = 0, minn = INF + 1;
    for (int i = 0; i < n; i++) {
        if (inputSeq[i] < minn) {
            minn = inputSeq[i];
            pos = i;
        }
    }
    int a = minn;
    int i = pos;
    do {
        if (inputSeq[i] <= n) {
            if (inputSeq[i] != a)
                return false;
        } else {
            if (frecv[inputSeq[i]])
                return false;
            frecv[inputSeq[i]]++;
        }
        a = a % n + 1;
        i = (i + 1) % n;
    } while (i != pos);

    return true;
}

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

int realVal[MAX_N];

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
    int pos = 0, minn = INF + 1;
    for (int i = 0; i < n; i++) {
        if (gondolaSeq[i] < minn) {
            minn = gondolaSeq[i];
            pos = i;
        }
    }
    int a = min(n, minn);
    int i = pos;
    vector<pair<int, int>> v;
    do {
        realVal[i] = a;
        a = a % n + 1;
        if (gondolaSeq[i] > n) 
            v.push_back({gondolaSeq[i], i});
        i = (i + 1) % n;
    } while (i != pos);

    int rep = n;
    sort(v.begin(), v.end());
    int l = 0;
    for (auto p: v) {
        replacementSeq[l++] = realVal[p.second];
        rep++;
        while (rep < p.first) {
            replacementSeq[l++] = rep;
            rep++;
        }
    }

    return l;
}

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

int countReplacement(int n, int inputSeq[]) {
    int pos = 0, minn = INF + 1;
    for (int i = 0; i < n; i++) {
        if (inputSeq[i] < minn) {
            minn = inputSeq[i];
            pos = i;
        }
    }

    int a = min(n, minn);
    int i = pos;
    vector<pair<int, int>> v;
    do {
        realVal[i] = a;
        if (inputSeq[i] <= n) {
            if (inputSeq[i] != a)
                return false;
        } else {
            if (frecv[inputSeq[i]])
                return false;
            frecv[inputSeq[i]]++;
        }
     
        a = a % n + 1;
        if (inputSeq[i] > n) 
            v.push_back({inputSeq[i], i});
        i = (i + 1) % n;
    } while (i != pos);

    int rep = n;
    sort(v.begin(), v.end());
    int all = v.size();
    int ans = 1;
    for (auto p: v) {
        int lib = p.first - rep - 1;
        rep = p.first;
        ans = (long long)ans * lgput(all, lib) % MOD; 
        all--;
    }

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