oj.uz

Submission #582781

# Submission time Handle Problem Language Result Execution time Memory
582781 2022-06-24T12:10:03 Z drdilyor Gondola (IOI14_gondola) C++17
100 / 100
 62 ms 6428 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
#ifdef ONPC
    #define cerr cout
    #include "t_debug.cpp"
#else
    #define debug(...) 42
#endif
#define allit(a) (a).begin(), (a).end()
#define sz(a) ((int) (a).size())
#define cut(s) {cout << s << '\n'; return 0;}
#include "gondola.h"

using namespace std;
using ll = long long;
using vi = vector<int>;
namespace pd = __gnu_pbds;
template<typename K> using ordered_set = pd::tree<K, pd::null_type, less<K>, pd::rb_tree_tag, pd::tree_order_statistics_node_update>;
template<typename... T> using hash_table = pd::gp_hash_table<T...>;

const int INF = 1e9;
const ll INFL = 1e18;
const int N = 250000;
const int MOD = 1e9+9;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rng(RANDOM);

int valid(int n, int* a_) {
    vi a(n);
    for (int i = 0; i < n; i++) a[i] = a_[i];

    set<int> unique = set<int>(a.begin(), a.end());
    if (unique.size() != a.size()) return 0;

    int start = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] <= n) {
            start = i - a[i] + 1;
            if (start < 0) start += n;
            break;
        }
    }
    rotate(a.begin(), a.begin()+start, a.end());
    for (int i = 0; i < n;  i++) {
        if (a[i] <= n && a[i] != i+1) return 0;
    }

    return 1;
}

int replacement(int n, int a_[], int b[]) {
    vi a(n), orig(n);
    int mxi = 0, start = 0;
    for (int i = 0; i < n; i++) {
        a[i] = a_[i];
        if (a[i] > a[mxi]) mxi = i;
        if (a[i] <= n) start = (i-a[i]+1 + n)%n;
        orig[i] = i+1;
    }
    rotate(orig.begin(), orig.begin()+(n-start), orig.end());

    int off = (n+1);
    memset(b, -1, sizeof(int) * (a[mxi] - n));
    for (int i = 0; i < n; i++) {
        if (a[i] != orig[i]) b[a[i]-off] = orig[i];
    }
    int spare = orig[mxi];
    for (int i = n+1; i <= a[mxi]; i++) {
        if (b[i-off] == -1) {
            b[i-off] = spare;
            spare = i;
        }
    }
    b[a[mxi]-off] = spare;
    return a[mxi] - n;
}

ll modpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b&1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

int countReplacement(int n, int inputSeq[]) {
    if (!valid(n, inputSeq)) return 0;
    vi a(n);
    for (int i = 0; i < n; i++) a[i] = inputSeq[i];
    sort(a.begin(), a.end());
    ll res = 1;
    int i = lower_bound(a.begin(), a.end(), n+1) - a.begin();
    for (; i < n; i++) {
        int remain = n - i;
        int len = a[i] - 1 - max(n, i?a[i-1]:0);
        res = res * modpow(remain, len) % MOD;
        debug(a, i, remain,len, res);
    }
    if (a.front() > n) res = res * n % MOD;
    return res;
}

Compilation message

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:8:24: warning: statement has no effect [-Wunused-value]
    8 |     #define debug(...) 42
      |                        ^~
gondola.cpp:100:9: note: in expansion of macro 'debug'
  100 |         debug(a, i, remain,len, res);
      |         ^~~~~

Subtask #1
5.0 / 5.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 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 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 212 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 7 ms 2260 KB Output is correct
7 Correct 37 ms 3924 KB Output is correct
8 Correct 22 ms 4116 KB Output is correct
9 Correct 5 ms 1492 KB Output is correct
10 Correct 20 ms 4760 KB Output is correct

Subtask #3
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 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 7 ms 2388 KB Output is correct
7 Correct 26 ms 3992 KB Output is correct
8 Correct 21 ms 4148 KB Output is correct
9 Correct 4 ms 1492 KB Output is correct
10 Correct 17 ms 4820 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 15 ms 2132 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 41 ms 4960 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 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

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 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 2 ms 340 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 2 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 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 212 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 8 ms 1196 KB Output is correct
12 Correct 9 ms 1368 KB Output is correct
13 Correct 15 ms 1060 KB Output is correct
14 Correct 7 ms 1236 KB Output is correct
15 Correct 18 ms 2128 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 1 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 1 ms 212 KB Output is correct
6 Correct 1 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 1 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 1 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 36 ms 4316 KB Output is correct
10 Correct 30 ms 3560 KB Output is correct
11 Correct 11 ms 1492 KB Output is correct
12 Correct 12 ms 1748 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 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 0 ms 212 KB Output is correct
9 Correct 32 ms 4308 KB Output is correct
10 Correct 28 ms 3660 KB Output is correct
11 Correct 9 ms 1492 KB Output is correct
12 Correct 11 ms 1748 KB Output is correct
13 Correct 3 ms 596 KB Output is correct
14 Correct 47 ms 5656 KB Output is correct
15 Correct 62 ms 6428 KB Output is correct
16 Correct 8 ms 1344 KB Output is correct
17 Correct 33 ms 4428 KB Output is correct
18 Correct 17 ms 2508 KB Output is correct