답안 #936485

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
936485 2024-03-02T00:57:11 Z peterandvoi 곤돌라 (IOI14_gondola) C++17
컴파일 오류
0 ms 0 KB
#include <bits/stdc++.h>

//#include "gondola.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 bin_pow(int a, int b) {
    int res = 1;
    for (; b; b >>= 1, a = 1LL * a * a % MOD) {
        if (b & 1) {
            res = 1LL * res * a % MOD;
        }
    }
    return res;
}

int countReplacement(int n, int inputSeq[]) {
    set<int> pos;
    for (int i = 0; i < n; ++i) {
        if (pos.find(inputSeq[i]) != pos.end()) {
            return 0;
        }
        pos.insert(inputSeq[i]);
    }
    int cnt = n;
    for (int i = 0; i < n; ++i) {
        if (inputSeq[i] <= n) {
            cnt--;
            pos.erase(inputSeq[i]);
        }
    }
    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) {
        if (inputSeq[i] <= n && inputSeq[i] != shift(i + 1, delta, n)) {
            return 0;
        }
        inputSeq[i] = shift(i + 1, delta, n);
    }
    if (cnt == n) {
        for (int i = 1; i <= n; ++i) {
            res = 1LL * res * i % MOD;
        }
    }
    int p = n;
    for (int j : pos) {
        res = 1LL * res * bin_pow(cnt, j - 1 - p) % MOD;
        p = j;
        cnt--;
    }
    return res;
}

Compilation message

/usr/bin/ld: /tmp/cczx3PWi.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