oj.uz

Submission #592961

# Submission time Handle Problem Language Result Execution time Memory
592961 2022-07-09T23:16:52 Z skittles1412 Gondola (IOI14_gondola) C++17
100 / 100
 40 ms 5196 KB 
#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())

extern "C" int valid(int n, int arr[]) {
    int x = -1;
    for (int i = 0; i < n; i++) {
        if (arr[i] <= n) {
            int cx = (arr[i] - i + n) % n;
            if (x == -1) {
                x = cx;
            } else if (x != cx) {
                return false;
            }
        }
    }
    set<int> s;
    for (int i = 0; i < n; i++) {
        s.insert(arr[i]);
    }
    return sz(s) == n;
}

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)) {
        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

# Verdict Execution time Memory 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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 212 KB Output is correct
6 Correct 10 ms 2132 KB Output is correct
7 Correct 10 ms 696 KB Output is correct
8 Correct 20 ms 3864 KB Output is correct
9 Correct 7 ms 1364 KB Output is correct
10 Correct 22 ms 4500 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory 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 11 ms 2132 KB Output is correct
7 Correct 7 ms 596 KB Output is correct
8 Correct 17 ms 3944 KB Output is correct
9 Correct 6 ms 1364 KB Output is correct
10 Correct 22 ms 4436 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 4 ms 340 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 8 ms 596 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory 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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory 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 1 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 22 ms 4492 KB Output is correct
12 Correct 31 ms 5196 KB Output is correct
13 Correct 22 ms 2988 KB Output is correct
14 Correct 21 ms 4484 KB Output is correct
15 Correct 25 ms 3112 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory Grader output
1 Correct 0 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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory 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 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 30 ms 4028 KB Output is correct
10 Correct 24 ms 3384 KB Output is correct
11 Correct 8 ms 1364 KB Output is correct
12 Correct 12 ms 1704 KB Output is correct
13 Correct 3 ms 596 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory 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 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 29 ms 3944 KB Output is correct
10 Correct 23 ms 3372 KB Output is correct
11 Correct 8 ms 1364 KB Output is correct
12 Correct 10 ms 1692 KB Output is correct
13 Correct 3 ms 596 KB Output is correct
14 Correct 36 ms 4508 KB Output is correct
15 Correct 40 ms 5008 KB Output is correct
16 Correct 8 ms 1304 KB Output is correct
17 Correct 29 ms 3540 KB Output is correct
18 Correct 15 ms 2100 KB Output is correct