oj.uz

Submission #592960

# Submission time Handle Problem Language Result Execution time Memory
592960 2022-07-09T23:11:05 Z skittles1412 Gondola (IOI14_gondola) C++17
100 / 100
 28 ms 5188 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())

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

# 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

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

# 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 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

# 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

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

# 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 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

# 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 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

# 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 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

# 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 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