oj.uz

Submission #818250

# Submission time Handle Problem Language Result Execution time Memory
818250 2023-08-10T04:10:50 Z andecaandeci Gondola (IOI14_gondola) C++17
100 / 100
 52 ms 6608 KB 
#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second

const int N = 3e5 + 5;
const int mod = 1e9 + 9;

// int gondolaSequence[100001];
// int replacementSequence[250001];
int ans[N];
set<int> s;

ll binpow(ll x, ll y) {
    if (y == 0) return 1;
    ll res = binpow(x, y / 2);
    res = (res * res) % mod;
    if (y % 2) res = (res * x) % mod;
    return res;
}

int valid(int n, int inputSeq[]) {
    int id1 = 0, id2 = 0;
    for (int i = 0; i < n; i++) {
        if (s.count(inputSeq[i])) return 0;
        s.insert(inputSeq[i]);
    }
    for (int i = 0; i < n; i++) {
        if (inputSeq[i] <= n) {
            id1 = inputSeq[i];
            id2 = i;
            break;
        }
    }
    if (id1 == 0) return 1;
    id2 -= id1 - 1;
    if (id2 < 0) id2 += n;
    for (int i = id2; i < id2 + n; i++) {
        if (inputSeq[i % n] > n) continue;
        if (i - id2 != inputSeq[i % n] - 1) return 0;
    }
    return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
    int id1 = 1, id2 = 0;
    for (int i = 0; i < n; i++) {
        if (gondolaSeq[i] <= n) {
            id1 = gondolaSeq[i];
            id2 = i;
            break;
        }
    }
    id2 -= id1 - 1;
    if (id2 < 0) id2 += n;
    int len = 0, id3 = -1, mx = 0;
    for (int i = 0; i < n; i++) {
        if (gondolaSeq[i] <= n) continue;
        mx = max(mx, gondolaSeq[i]);
        if (gondolaSeq[i] == mx) id3 = i;
        ans[gondolaSeq[i]] = ((i + n - id2) % n) + 1;
    }
    if (id3 == -1) return 0;
    ans[gondolaSeq[id3]] = 0;
    id3 = ((id3 + n - id2) % n) + 1;
    int ans2 = id3, target = n + 1;
    while (target <= mx) {
        if (ans[target] == 0) {
            replacementSeq[len] = ans2;
            ans2 = target; 
        } 
        else replacementSeq[len] = ans[target];
        len++, target++;
    }
    return len;
}

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

int countReplacement(int n, int inputSeq[]) {
    if (!valid(n, inputSeq)) return 0;
    vector<int> v;
    for (int i = 0; i < n; i++) if (inputSeq[i] > n) v.push_back(inputSeq[i]);
    sort(v.begin(), v.end());
    ll answ = 1, cnt = (int)v.size(), tmp = n + 1;
    if (cnt == n) answ = n;   
    for (auto x : v) {
        answ *= binpow(cnt, x - tmp);
        answ %= mod;
        tmp = x + 1;
        cnt--;
    }
    return answ;
}

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 308 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 304 KB Output is correct
4 Correct 0 ms 308 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 10 ms 2388 KB Output is correct
7 Correct 7 ms 1088 KB Output is correct
8 Correct 19 ms 4300 KB Output is correct
9 Correct 6 ms 1492 KB Output is correct
10 Correct 24 ms 4904 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 1 ms 292 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 10 ms 2388 KB Output is correct
7 Correct 8 ms 1128 KB Output is correct
8 Correct 19 ms 4360 KB Output is correct
9 Correct 7 ms 1588 KB Output is correct
10 Correct 26 ms 4972 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 14 ms 2344 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 31 ms 5140 KB Output is correct

Subtask #4
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 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 #5
10.0 / 10.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 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 1 ms 212 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 304 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 1 ms 212 KB Output is correct
2 Correct 1 ms 308 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 308 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 336 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 6 ms 1048 KB Output is correct
12 Correct 6 ms 1136 KB Output is correct
13 Correct 13 ms 1620 KB Output is correct
14 Correct 6 ms 1052 KB Output is correct
15 Correct 21 ms 2660 KB Output is correct

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

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 304 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 304 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 308 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 1 ms 308 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 304 KB Output is correct
9 Correct 38 ms 4876 KB Output is correct
10 Correct 28 ms 4140 KB Output is correct
11 Correct 11 ms 1712 KB Output is correct
12 Correct 11 ms 2112 KB Output is correct
13 Correct 3 ms 700 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 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 1 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 212 KB Output is correct
9 Correct 34 ms 4796 KB Output is correct
10 Correct 28 ms 4124 KB Output is correct
11 Correct 10 ms 1824 KB Output is correct
12 Correct 11 ms 2068 KB Output is correct
13 Correct 3 ms 704 KB Output is correct
14 Correct 43 ms 5972 KB Output is correct
15 Correct 52 ms 6608 KB Output is correct
16 Correct 8 ms 1560 KB Output is correct
17 Correct 32 ms 4540 KB Output is correct
18 Correct 14 ms 2884 KB Output is correct