oj.uz

Submission #620486

# Submission time Handle Problem Language Result Execution time Memory
620486 2022-08-03T06:25:41 Z Genius3435 Gondola (IOI14_gondola) C++17
100 / 100
 71 ms 5912 KB 
#include <bits/stdc++.h>
using namespace std;

#include "gondola.h"
 
constexpr int N = 100005;
constexpr int M = 250005;
constexpr int MOD = 1000000009;
 
int valid(int n, int a[]) {
    // Check that values \leq n are in order, and that there are no repeats
 
    set<int> contained;
    for (int i = 0; i < n; ++i) {
        if (contained.count(a[i])) return 0;
        contained.insert(a[i]);
    }
 
 
    int start_index = -1;
    for (int i = 0; i < n; ++i) {
        if (a[i] <= n) {
            int index = (a[i] - (i+1) + n) % n;
            if (start_index == -1) {
                start_index = index;
            } else if (start_index != index) {
                return 0;
            }
        }
    }
 
    return 1;
}
 
 
 
int replacement(int n, int a[], int b[]) {
    static int position[M];
    auto it = max_element(a, a+n);
    int m = *it, max_idx = it-a;
    for (int i = 1; i <= m; ++i) {
        position[i] = -1;
    }
    for (int i = 0; i < n; ++i) {
        position[a[i]] = i;
    }
 
 
    int start_index = -1;
    for (int i = 0; i < n; ++i) {
        if (a[i] <= n) {
            start_index = (a[i] - (i+1) + n) % n;
            break;
        }
    }
    if (start_index == -1) {
        start_index = 0;
    }
 
 
    int *currSeq = new int[n];
    for (int i = 0; i < n; ++i) {
        currSeq[i] = (start_index + i) % n + 1;
    }
 
    for (int i = n+1; i <= m; ++i) {
        if (position[i] == -1) {
            b[i-n-1] = currSeq[max_idx];
            currSeq[max_idx] = i;
        } else {
            b[i-n-1] = currSeq[position[i]];
            currSeq[position[i]] = i;
        }
    }
 
    delete[] currSeq;
 
    return m-n;
}
 
 
 
int pow(long long b, int e, int m) {
    long long p = 1;
    while (e) {
        if (e&1) p = p * b % m;
        e >>= 1, b = b * b % m;
    }
    return p;
}
 
int countReplacement(int n, int a[]) {
    if (!valid(n, a)) return 0;
 
    std::set<int> contained;
    for (int i = 0; i < n; ++i) {
        if (a[i] > n) {
            contained.insert(a[i]);
        }
    }
 
    int positions = contained.size();
    long long ans = positions<n ? 1 : n;
    int prv = n;
    for (const int i : contained) {
        // All values in the interval (prv, i) have positions spots they could go in
        ans = ans * pow(positions, i-prv-1, MOD) % MOD;
        prv = i;
        positions--;
    }
    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 304 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 13 ms 2392 KB Output is correct
7 Correct 9 ms 1148 KB Output is correct
8 Correct 25 ms 4228 KB Output is correct
9 Correct 9 ms 1604 KB Output is correct
10 Correct 33 ms 5136 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 304 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 15 ms 2496 KB Output is correct
7 Correct 11 ms 1188 KB Output is correct
8 Correct 23 ms 4264 KB Output is correct
9 Correct 9 ms 1500 KB Output is correct
10 Correct 39 ms 4972 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 14 ms 2376 KB Output is correct
14 Correct 1 ms 304 KB Output is correct
15 Correct 37 ms 5152 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 308 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 468 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 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 308 KB Output is correct
7 Correct 1 ms 308 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 9 ms 1624 KB Output is correct
12 Correct 14 ms 1856 KB Output is correct
13 Correct 10 ms 1736 KB Output is correct
14 Correct 8 ms 1620 KB Output is correct
15 Correct 16 ms 3028 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 312 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 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 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 304 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 308 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 308 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 57 ms 4452 KB Output is correct
10 Correct 40 ms 3732 KB Output is correct
11 Correct 14 ms 1588 KB Output is correct
12 Correct 17 ms 1876 KB Output is correct
13 Correct 4 ms 608 KB Output is correct

Subtask #10
10.0 / 10.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 308 KB Output is correct
4 Correct 1 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 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 53 ms 4508 KB Output is correct
10 Correct 38 ms 3788 KB Output is correct
11 Correct 13 ms 1524 KB Output is correct
12 Correct 17 ms 1804 KB Output is correct
13 Correct 6 ms 628 KB Output is correct
14 Correct 71 ms 5304 KB Output is correct
15 Correct 71 ms 5912 KB Output is correct
16 Correct 10 ms 1364 KB Output is correct
17 Correct 45 ms 4032 KB Output is correct
18 Correct 27 ms 2368 KB Output is correct