제출 #1149150

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1149150		BlockOG	곤돌라 (IOI14_gondola)	C++20	60 / 100	17 ms	1216 KiB

gondola

#include "gondola.h"
#include <queue>
#include <utility>

// meeeow mrrowww :3
// go play vivid/stasis! it's a very awesome free game on steam

using namespace std;

int valid(int n, int inputSeq[]) {
    int offset_got = false, offset;
    for (int i = 0; i < n; i++) {
        if (inputSeq[i] <= n) {
            if (offset_got) {
                if ((inputSeq[i] + offset + n) % n != i) return false;
            } else {
                offset_got = true;
                offset = i - inputSeq[i];
            }
        }
    }

    return true;
}

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
    int fixedSeq[n];

    int offset_got = false, offset;
    for (int i = 0; i < n; i++) {
        if (offset_got) {
            fixedSeq[i] = (i - offset - 1 + n) % n + 1;
        } else if (gondolaSeq[i] <= n) {
            offset_got = true;
            offset = i - gondolaSeq[i];
            for (int j = 0; j <= i; j++) fixedSeq[j] = (j - offset - 1 + n) % n + 1;
        }
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    for (int i = 0; i < n; i++) {
        if (gondolaSeq[i] > n) q.emplace(gondolaSeq[i] - n, fixedSeq[i]);
    }

    int l = 0;
    while (q.size()) {
        auto [m, r] = q.top();
        q.pop();

        for (int i = 0; i < m; i++) {
            replacementSeq[l++] = r;
            r = n + l;
        }
    }

    return l;
}

long long pow(long long a, long long b) {
    long long res = 1;

    while (b) {
        if (b & 1) { res = (res * a) % 1000000009; }

        a = (a * a) % 1000000009;
        b >>= 1;
    }

    return res;
}

int countReplacement(int n, int inputSeq[]) {
    int offset_got = false, offset;
    priority_queue<int, vector<int>, greater<int>> q;
    for (int i = 0; i < n; i++) {
        if (inputSeq[i] <= n) {
            if (offset_got) {
                if ((inputSeq[i] + offset + n) % n != i) return 0;
            } else {
                offset_got = true;
                offset = i - inputSeq[i];
            }
        } else {
            q.push(inputSeq[i]);
        }
    }

    long long res = 1;
    int p = n;
    while (q.size()) {
        int v = q.top();

        res = (res * pow(q.size(), v - p - 1)) % 1000000009;
        p = v;

        q.pop();
    }

    if (!offset_got) res = (res * n) % 1000000009;
    return res;
}

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