Submission #936320

# Submission time Handle Problem Language Result Execution time Memory
936320 2024-03-01T15:17:35 Z peterandvoi Gondola (IOI14_gondola) C++17
Compilation error
0 ms 0 KB
#include <bits/stdc++.h>

using namespace std;

#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 250005;

int cnt[N];

int shift(int i, int j, int n) {
    i += j;
    if (i < 1) {
        i += n;
    }
    if (i > n) {
        i -= n;
    }
    return i;
}

int valid(int n, int inputSeq[]) {
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < n; ++i) {
        assert(inputSeq[i] < N);
        if (cnt[inputSeq[i]]) {
            return 0;
        }
        cnt[inputSeq[i]]++;
    }
    int delta = 0;
    for (int i = 0; i < n; ++i) {
        if (inputSeq[i] <= n) {
            int j = inputSeq[i];
            delta = j - i - 1;
            break;
        }
    }
    for (int i = 0; i < n; ++i) {
        if (inputSeq[i] <= n) {
            int j = shift(i + 1, delta, n);
            if (j != inputSeq[i]) {
                return 0;
            }
        }
    }
    return 1;
}

int pos[N];

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
    memset(pos, -1, sizeof(pos));
    for (int i = 0; i < n; ++i) {
        pos[gondolaSeq[i]] = i;
    }
    set<int> cur;
    for (int i = 0; i < n; ++i) {
        cur.insert(i);
    }
    for (int i = 0; i < n; ++i) {
        if (gondolaSeq[i] <= n) {
            cur.erase(i);
        }
    }
    int delta = 0;
    for (int i = 0; i < n; ++i) {
        if (gondolaSeq[i] <= n) {
            int j = gondolaSeq[i];
            delta = j - i - 1;
            break;
        }
    }
    for (int i = 0; i < n; ++i) {
        gondolaSeq[i] = shift(i + 1, delta, n);
    }
    int m = -1;
    for (int i = n + 1; i < N; ++i) {
        if (!cur.size()) {
            break;
        }
        int j = *cur.begin();
        if (pos[i] != -1) {
            j = pos[i];
            cur.erase(j);
        }
        replacementSeq[++m] = gondolaSeq[j];
        gondolaSeq[j] = i;
    }
    return m + 1;
}

const int MOD = (int) 1e9 + 9;

int countReplacement(int n, int inputSeq[]) {
    if (valid(n, inputSeq) == 0) {
        return 0;
    }
    memset(pos, -1, sizeof(pos));
    for (int i = 0; i < n; ++i) {
        pos[inputSeq[i]] = i;
    }
    int cnt = n;
    for (int i = 0; i < n; ++i) {
        if (inputSeq[i] <= n) {
            cnt--;
        }
    }
    int res = 1;
    int delta = 0;
    for (int i = 0; i < n; ++i) {
        if (inputSeq[i] <= n) {
            int j = inputSeq[i];
            delta = j - i - 1;
            break;
        }
    }
    for (int i = 0; i < n; ++i) {
        inputSeq[i] = shift(i + 1, delta, n);
    }
    if (n == 2 && cnt < 2) {
        return 1;
    }
    for (int i = n + 1; i < N; ++i) {
        if (!cnt) {
            break;
        }
        if (pos[i] != -1) {
            cnt--;
        } else {
            res = 1LL * res * cnt % MOD;
        }
    }
    if (n == 2) {
        res = 1LL * res * 2 % MOD;
    }
    return res;
}

Compilation message

/usr/bin/ld: /tmp/ccQWSQp7.o: in function `main':
grader.cpp:(.text.startup+0xb6): undefined reference to `valid'
/usr/bin/ld: grader.cpp:(.text.startup+0x108): undefined reference to `countReplacement'
/usr/bin/ld: grader.cpp:(.text.startup+0x132): undefined reference to `replacement'
collect2: error: ld returned 1 exit status