Submission #676849

#	Time	Username	Problem	Language	Result	Execution time	Memory
676849		bashkort	Gondola (IOI14_gondola)	C++17	100 / 100	31 ms	6888 KiB

gondola

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

using namespace std;

constexpr int X = 1e6 + 1, N = 250001, MOD = 1e9 + 9;
int inv[X], tmp[N];

int valid(int n, int inputSeq[]) {
    memset(inv, -1, sizeof(inv));
    for (int i = 0; i < n; ++i) {
        if (inputSeq[i] <= n) {
            inv[inputSeq[i]] = i;
        }
    }
    memcpy(tmp, inputSeq, sizeof(tmp[0]) * n);
    sort(tmp, tmp + n);
    if (unique(tmp, tmp + n) != tmp + n) {
        return 0;
    }
    int offset = -1;
    for (int x = 1; x <= n; ++x) {
        if (inv[x] != -1) {
            int now = x - inv[x];
            if (now < 0) now += n;
            if (offset != -1 && offset != now) {
                return 0;
            }
            offset = now;
        }
    }
    return 1;
}

int replacement(int n, int inputSeq[], int replacementSeq[]) {
    memset(inv, -1, sizeof(inv));
    const int A = *max_element(inputSeq, inputSeq + n);
    if (A == n) {
        return 0;
    }
    for (int i = 0; i < n; ++i) {
        if (inv[inputSeq[i]] != -1) {
            return 0;
        }
        inv[inputSeq[i]] = i;
    }
    int offset = -1;
    for (int x = 1; x <= n; ++x) {
        if (inv[x] != -1) {
            int now = x - inv[x];
            if (now < 0) now += n;
            if (offset != -1 && offset != now) {
                return 0;
            }
            offset = now;
        }
    }

    vector<int> initial(n);
    if (offset == -1) {
        iota(initial.begin(), initial.end(), 1);
    } else {
        for (int x = 1; x <= n; ++x) {
            int i = x - offset;
            if (i < 0) i += n;
            initial[i] = x;
        }
    }

    set<int> st;
    for (int i = 0; i < n; ++i) {
        if (inputSeq[i] != initial[i]) {
            st.insert(i);
        }
    }

    int l = 0;
    for (int x = n + 1; x <= A; ++x) {
        int i;
        if (inv[x] != -1) {
            i = inv[x];
        } else {
            i = *st.begin();
        }
        replacementSeq[l++] = initial[i];
        initial[i] = x;
        if (initial[i] == inputSeq[i]) {
            st.erase(i);
        }
    }
    return l;
}

int power(int a, int b) {
    int res = 1;
    for (; b > 0; b >>= 1, a = 1LL * a * a % MOD) {
        if (b & 1) {
            res = 1LL * a * res % MOD;
        }
    }
    return res;
}

int countReplacement(int n, int inputSeq[]) {
    if (!valid(n, inputSeq)) {
        return 0;
    }
    memset(inv, -1, sizeof(inv));
    const int A = *max_element(inputSeq, inputSeq + n);
    for (int i = 0; i < n; ++i) {
        if (inputSeq[i] <= n) {
            inv[inputSeq[i]] = i;
        }
    }
    int offset = -1;
    for (int x = 1; x <= n; ++x) {
        if (inv[x] != -1) {
            int now = x - inv[x];
            if (now < 0) now += n;
            if (offset != -1 && offset != now) {
                return 0;
            }
            offset = now;
        }
    }

    vector<int> initial(n);
    constexpr int MOD = 1e9 + 9;
    int ans = 1;
    if (offset == -1) {
        iota(initial.begin(), initial.end(), 1);
        ans = n;
    } else {
        for (int x = 1; x <= n; ++x) {
            int i = x - offset;
            if (i < 0) i += n;
            initial[i] = x;
        }
    }

    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (inputSeq[i] != initial[i]) {
            cnt += 1;
        }
    }
    sort(inputSeq, inputSeq + n);

    int last = n;
    for (int ii = 0; ii < n; ++ii) {
        int x = inputSeq[ii];
        if (x <= n) {
            continue;
        }
        ans = 1LL * ans * power(cnt, x - last - 1) % MOD;
        last = x;
        cnt -= 1;
    }
    return ans;
}

Compilation message (stderr)

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:109:15: warning: unused variable 'A' [-Wunused-variable]
  109 |     const int A = *max_element(inputSeq, inputSeq + n);
      |               ^

• 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