답안 #592960

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
592960	2022-07-09T23:11:05 Z	skittles1412	곤돌라 (IOI14_gondola)	C++17	100 / 100	28 ms	5188 KB

gondola

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__);
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

bool valid(int n, int arr[], bool wtf) {
    int x = -1;
    for (int i = 0; i < n; i++) {
        if (wtf || arr[i] <= n) {
            int cx = (arr[i] - i + n) % n;
            if (x == -1) {
                x = cx;
            } else if (x != cx) {
                return false;
            }
        }
    }
    return true;
}

extern "C" int valid(int n, int arr[]) {
    return valid(n, arr, true);
}

extern "C" int replacement(int n, int arr[], int out[]) {
    int targ[n];
    int x = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] <= n) {
            x = arr[i] - i;
        }
    }
    for (int i = 0; i < n; i++) {
        targ[i] = (x + i + n) % n;
        if (!targ[i]) {
            targ[i] = n;
        }
        dbg(targ[i]);
    }
    map<int, int> rev;
    for (int i = 0; i < n; i++) {
        rev[arr[i]] = i;
    }
    vector<int> ans;
    int mind = max_element(arr, arr + n) - arr, e = arr[mind];
    for (int i = n + 1; i <= e; i++) {
        auto it = rev.find(i);
        int cind;
        if (it == rev.end()) {
            cind = mind;
        } else {
            cind = it->second;
        }
        ans.push_back(targ[cind]);
        targ[cind] = i;
    }
    copy(begin(ans), end(ans), out);
    return sz(ans);
}

const long mod = 1e9 + 9;

long bpow(long base, long exp) {
    long ans = 1;
    while (exp) {
        if (exp & 1) {
            ans = (ans * base) % mod;
        }
        base = (base * base) % mod;
        exp >>= 1;
    }
    return ans;
}

extern "C" int countReplacement(int n, int arr[]) {
    if (!valid(n, arr, false)) {
        return 0;
    }
    sort(arr, arr + n);
    long ans = 1;
    if (arr[0] > n) {
        ans = n;
    }
    vector<int> cur {n};
    for (int i = 0; i < n; i++) {
        if (arr[i] > n) {
            cur.push_back(arr[i]);
        }
    }
    for (int i = 0; i < sz(cur) - 1; i++) {
        ans = (ans * bpow(sz(cur) - i - 1, cur[i + 1] - cur[i] - 1)) % mod;
        dbg(ans);
    }
    return ans;
}

Subtask #1
5.0 / 5.0

#	결과	메모리	Grader output
1	Correct	212 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Correct	212 KB	Output is correct
4	Correct	212 KB	Output is correct
5	Correct	212 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	3 ms	340 KB	Output is correct
7	Correct	7 ms	552 KB	Output is correct
8	Correct	6 ms	468 KB	Output is correct
9	Correct	2 ms	360 KB	Output is correct
10	Correct	7 ms	596 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	3 ms	340 KB	Output is correct
7	Correct	11 ms	636 KB	Output is correct
8	Correct	7 ms	468 KB	Output is correct
9	Correct	3 ms	340 KB	Output is correct
10	Correct	7 ms	596 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	3 ms	340 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	7 ms	616 KB	Output is correct

Subtask #4
5.0 / 5.0

#	결과	메모리	Grader output
1	Correct	212 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Correct	212 KB	Output is correct
4	Correct	212 KB	Output is correct
5	Correct	212 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	28 ms	4544 KB	Output is correct
12	Correct	23 ms	5188 KB	Output is correct
13	Correct	25 ms	2932 KB	Output is correct
14	Correct	21 ms	4564 KB	Output is correct
15	Correct	24 ms	3076 KB	Output is correct

Subtask #7
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct

Subtask #8
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	12 ms	980 KB	Output is correct
10	Correct	10 ms	920 KB	Output is correct
11	Correct	4 ms	604 KB	Output is correct
12	Correct	5 ms	596 KB	Output is correct
13	Correct	2 ms	340 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	13 ms	980 KB	Output is correct
10	Correct	13 ms	852 KB	Output is correct
11	Correct	4 ms	528 KB	Output is correct
12	Correct	5 ms	596 KB	Output is correct
13	Correct	2 ms	340 KB	Output is correct
14	Correct	16 ms	1228 KB	Output is correct
15	Correct	17 ms	1232 KB	Output is correct
16	Correct	3 ms	468 KB	Output is correct
17	Correct	12 ms	852 KB	Output is correct
18	Correct	6 ms	832 KB	Output is correct

답안 #592960

Compilation message