oj.uz

Submission #623392

# Submission time Handle Problem Language Result Execution time Memory
623392 2022-08-05T14:12:30 Z yuto1115 Gondola (IOI14_gondola) C++17
100 / 100
 50 ms 5928 KB 
#include "gondola.h"
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); ++i)
#define rrep(i, n) for(ll i = ll(n) - 1; i >= 0; --i)
#define rrep2(i, n, t) for(ll i = ll(n) - 1; i >= ll(t); --i)
#define pb push_back
#define eb emplace_back
#define SZ(a) int(a.size())
#define all(a) a.begin(), a.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
const int inf = 1001001001;
const ll linf = 1001001001001001001;

template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

int valid(int n, int inputSeq[]) {
    int p1 = -1;
    set<int> st;
    rep(i, n) {
        int now = inputSeq[i];
        if (st.count(now)) return 0;
        st.insert(now);
        if (now <= n) {
            int p = (i - (now - 1) + n) % n;
            if (p1 != -1 and p1 != p) return 0;
            p1 = p;
        }
    }
    return 1;
}

//----------------------

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
    int p1 = -1;
    int mx = n, mx_id = -1;
    rep(i, n) {
        int now = gondolaSeq[i];
        if (chmax(mx, now)) mx_id = i;
        if (now <= n) {
            int p = (i - (now - 1) + n) % n;
            assert(p1 == -1 or p1 == p);
            p1 = p;
        }
    }
    if (mx == n) return 0;
    if (p1 == -1) p1 = 0;
    vi pre(mx + 1, -1);
    rep(i, n) {
        if (i == mx_id or gondolaSeq[i] <= n) continue;
        pre[gondolaSeq[i]] = 1 + (i - p1 + n) % n;
    }
    int now = 1 + (mx_id - p1 + n) % n;
    rep2(i, n + 1, mx + 1) {
        if (pre[i] == -1) {
            pre[i] = now;
            now = i;
        }
        replacementSeq[i - (n + 1)] = pre[i];
    }
    return mx - n;
}

//----------------------

const int mod = 1000000009;

ll mod_pow(ll a, int t) {
    ll res = 1;
    while (t) {
        if (t & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        t >>= 1;
    }
    return res;
}

int countReplacement(int n, int inputSeq[]) {
    if (!valid(n, inputSeq)) return 0;
    vi v = {n};
    rep(i, n) if (inputSeq[i] > n) v.pb(inputSeq[i]);
    sort(all(v));
    ll res = 1;
    rep2(i, 1, SZ(v)) {
        res *= mod_pow(SZ(v) - i, v[i] - v[i - 1] - 1);
        res %= mod;
    }
    if (SZ(v) > n) res = (res * n) % mod;
    return res;
}

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 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 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 13 ms 2260 KB Output is correct
7 Correct 7 ms 596 KB Output is correct
8 Correct 22 ms 3872 KB Output is correct
9 Correct 7 ms 1364 KB Output is correct
10 Correct 29 ms 4480 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 12 ms 2132 KB Output is correct
7 Correct 7 ms 540 KB Output is correct
8 Correct 21 ms 3924 KB Output is correct
9 Correct 7 ms 1364 KB Output is correct
10 Correct 29 ms 4512 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 596 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 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

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 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 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 0 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 7 ms 596 KB Output is correct
12 Correct 8 ms 596 KB Output is correct
13 Correct 10 ms 1108 KB Output is correct
14 Correct 7 ms 528 KB Output is correct
15 Correct 18 ms 2040 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 0 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 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 312 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 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 308 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 38 ms 4436 KB Output is correct
10 Correct 27 ms 3660 KB Output is correct
11 Correct 10 ms 1492 KB Output is correct
12 Correct 13 ms 1844 KB Output is correct
13 Correct 3 ms 572 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 316 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 35 ms 4496 KB Output is correct
10 Correct 28 ms 3764 KB Output is correct
11 Correct 11 ms 1492 KB Output is correct
12 Correct 13 ms 1872 KB Output is correct
13 Correct 3 ms 596 KB Output is correct
14 Correct 46 ms 5424 KB Output is correct
15 Correct 50 ms 5928 KB Output is correct
16 Correct 8 ms 1364 KB Output is correct
17 Correct 33 ms 4048 KB Output is correct
18 Correct 17 ms 2360 KB Output is correct