oj.uz

Submission #391937

# Submission time Handle Problem Language Result Execution time Memory
391937 2021-04-20T08:07:57 Z Aldas25 Gondola (IOI14_gondola) C++14
100 / 100
 42 ms 6204 KB 
#include "gondola.h"
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<int> vi;


int valid(int n, int inputSeq[])
{
    FOR(i, 0, n-1) inputSeq[i]--;

    unordered_set<int> cont;
    FOR(i, 0, n-1) cont.insert(inputSeq[i]);
    if ((int)cont.size() < n) return false;

    int ch = -1;
    FOR(i, 0, n-1) {
        if (inputSeq[i] >= n) continue;
        ch = i;
        break;
    }

    if (ch == -1) return true;

    FOR(i, 0, n-1) {
        int id = (ch+i)%n;
        if (inputSeq[id] >= n) continue;
        int shouldBe = (inputSeq[ch]+i)%n;
        if (inputSeq[id] != shouldBe) return false;
    }

    return true;
}

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

int replacement(int n, int inputSeq[], int replacementSeq[])
{
    FOR(i, 0, n-1) inputSeq[i]--;

    int l = 0;

    int ch = 0;
    FOR(i, 0, n-1) {
        if (inputSeq[i] >= n) continue;
        ch = i;
        break;
    }

    int cur[n];

    cur[ch] = (inputSeq[ch] < n ? inputSeq[ch] : 0);

    FOR(i, 0, n-1) {
        int id = (ch+i)%n;
        int shouldBe = (cur[ch]+i)%n;
        cur[id] = shouldBe;
    }

    vii seq;
    FOR(i, 0, n-1) {
        seq.pb({inputSeq[i], i});
    }
    sort(seq.begin(), seq.end());

    int crAdd = n;
    for (auto p : seq) {
        int id = p.s;
        while (cur[id] < inputSeq[id]) {
            replacementSeq[l] = cur[id]+1;
            cur[id] = crAdd;
            crAdd++;
            l++;
        }
    }

    return l;
}

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

const ll MOD =  1000000009;

ll pwr (ll a, ll p) {
    if (p == 0) return 1ll;
    if (p == 1) return a%MOD;
    ll ret = pwr(a, p/2);
    ret = (ret*ret)%MOD;
    if (p%2 == 1) ret *= a%MOD;
    return ret%MOD;
}

int countReplacement(int n, int inputSeq[])
{
    ll ans = 1;

    vii seq;
    FOR(i, 0, n-1) {
        seq.pb({inputSeq[i], i});
    }
    sort(seq.begin(), seq.end());

    ll rem = n;
    ll lst = n;
    bool found = false;
    for (auto p : seq) {
        int id = p.s;
        if (inputSeq[id] > n) {
            ll cnt = inputSeq[id] - lst - 1;
            ll cr = pwr(rem, cnt);
            ans = (ans*cr)%MOD;
            lst = inputSeq[id];
        } else found = true;
        rem--;
    }

    if (!found) ans = (ans*n)%MOD;

    if (!valid(n, inputSeq)) return 0;

    return ans;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 10 ms 2116 KB Output is correct
7 Correct 26 ms 4024 KB Output is correct
8 Correct 17 ms 3984 KB Output is correct
9 Correct 5 ms 1352 KB Output is correct
10 Correct 19 ms 4152 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 9 ms 2128 KB Output is correct
7 Correct 25 ms 3984 KB Output is correct
8 Correct 17 ms 3928 KB Output is correct
9 Correct 5 ms 1356 KB Output is correct
10 Correct 21 ms 4208 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 10 ms 2040 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 24 ms 4304 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 16 ms 1988 KB Output is correct
12 Correct 17 ms 2172 KB Output is correct
13 Correct 22 ms 1380 KB Output is correct
14 Correct 19 ms 2008 KB Output is correct
15 Correct 28 ms 2292 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 30 ms 4984 KB Output is correct
10 Correct 24 ms 3708 KB Output is correct
11 Correct 9 ms 1572 KB Output is correct
12 Correct 11 ms 1864 KB Output is correct
13 Correct 3 ms 696 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 30 ms 5048 KB Output is correct
10 Correct 24 ms 3712 KB Output is correct
11 Correct 9 ms 1588 KB Output is correct
12 Correct 14 ms 1864 KB Output is correct
13 Correct 3 ms 588 KB Output is correct
14 Correct 37 ms 5704 KB Output is correct
15 Correct 42 ms 6204 KB Output is correct
16 Correct 8 ms 1480 KB Output is correct
17 Correct 29 ms 5060 KB Output is correct
18 Correct 16 ms 2760 KB Output is correct