oj.uz

Submission #374612

# Submission time Handle Problem Language Result Execution time Memory
374612 2021-03-07T15:18:21 Z vishesh312 Gondola (IOI14_gondola) C++17
100 / 100
 123 ms 5740 KB 
#include "bits/stdc++.h"
using namespace std;
#include "gondola.h"

int valid(int n, int arr[]) {
    map<int, bool> mp;
    vector<int> v(arr, arr+n);
    auto it = min_element(v.begin(), v.end());
    rotate(v.begin(), it, v.end());
    for (int i = 0; i < n; ++i) {
        if (mp[v[i]]) return 0;
        mp[v[i]] = true;
        if (v[i] <= n and i != v[i] - v[0]) return 0;
    }
    return 1;
}

int replacement(int n, int a[], int b[]) {
    vector<int> v(a, a+n);
    auto it = min_element(v.begin(), v.end());
    int mn = *it, pos = it - v.begin(), mx = *max_element(v.begin(), v.end());
    rotate(v.begin(), v.begin() + (pos - mn%n + 1 + n) % n, v.end());
    map<int, int> mp;
    for (int i = 0; i < n; ++i) {
        mp[v[i]] = i+1;
    }
    for (int i = n+1; i <= mx; ++i) {
        if (mp.count(i)) b[i-n-1] = mp[i];
        else {
            b[i-n-1] = mp[mx];
            mp[mx] = i;
        }
    }
    return mx - n;
}

using ll = long long;
const ll mod = 1e9+9;
#define sz(x) (int)x.size()

ll binexp(ll a, ll b) {
    a %= mod;
    ll ret = 1;
    while (b) {
        if (b&1) {
            ret = (ret * a) % mod;
        }
        a = (a * a) % mod;
        b >>= 1;
    }
    return ret;
}

int countReplacement(int n, int a[]) {
    vector<int> v(a, a+n);
    auto it = min_element(v.begin(), v.end());
    rotate(v.begin(), it, v.end());
    vector<int> v2 = v;
    sort(v2.begin(), v2.end());
    if (unique(v2.begin(), v2.end()) != v2.end()) return 0;
    for (int i = 0; i < n; ++i) {
        if (v[i] <= n and i != v[i] - v[0]) return 0;
    }
    ll ans;
    if (v2[0] > n) ans = n;
    else ans = 1;
    vector<int> bigger;
    bigger.push_back(n);
    for (int i = 0; i < n; ++i) if (v[i] > n) bigger.push_back(v[i]);
    sort(bigger.begin(), bigger.end());
    for (int i = 1; i < sz(bigger); ++i) {
        ans = (ans * binexp(sz(bigger) - i, bigger[i] - bigger[i-1] - 1)) % mod;
    }
    int ret = ans;
    return ret;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 15 ms 2412 KB Output is correct
7 Correct 13 ms 1004 KB Output is correct
8 Correct 30 ms 4204 KB Output is correct
9 Correct 9 ms 1516 KB Output is correct
10 Correct 36 ms 4844 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 16 ms 2412 KB Output is correct
7 Correct 11 ms 1004 KB Output is correct
8 Correct 31 ms 4204 KB Output is correct
9 Correct 9 ms 1516 KB Output is correct
10 Correct 36 ms 4844 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 5 ms 620 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 11 ms 1004 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 85 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 123 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 2 ms 364 KB Output is correct
11 Correct 26 ms 5100 KB Output is correct
12 Correct 29 ms 5740 KB Output is correct
13 Correct 34 ms 3044 KB Output is correct
14 Correct 27 ms 5100 KB Output is correct
15 Correct 39 ms 3148 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 23 ms 2188 KB Output is correct
10 Correct 18 ms 1772 KB Output is correct
11 Correct 7 ms 1004 KB Output is correct
12 Correct 9 ms 1004 KB Output is correct
13 Correct 3 ms 492 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 22 ms 2028 KB Output is correct
10 Correct 18 ms 1772 KB Output is correct
11 Correct 7 ms 1004 KB Output is correct
12 Correct 9 ms 1004 KB Output is correct
13 Correct 3 ms 492 KB Output is correct
14 Correct 28 ms 2792 KB Output is correct
15 Correct 32 ms 3048 KB Output is correct
16 Correct 6 ms 876 KB Output is correct
17 Correct 21 ms 2028 KB Output is correct
18 Correct 12 ms 1516 KB Output is correct