oj.uz

Submission #582965

# Submission time Handle Problem Language Result Execution time Memory
582965 2022-06-24T16:10:43 Z thezomb1e Gondola (IOI14_gondola) C++17
100 / 100
 54 ms 6020 KB 
#include "gondola.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
#define eb emplace_back
#define pb push_back
#define ft first
#define sd second
#define pi pair<int, int>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define dbg(...) dbg_out(__VA_ARGS__)
 
using ll = long long;
using ld = long double;
using namespace std;
using namespace __gnu_pbds;
 
//Constants
const ll INF = 5 * 1e18;
const int IINF = 2 * 1e9;
const ll MOD = 1e9 + 9;
// const ll MOD = 998244353;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ld PI = 3.14159265359;
 
//Templates
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) {return os << '(' << p.first << ", " << p.second << ')';}
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) {os << '['; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << ']';}
void dbg_out() {cerr << endl;}
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << H << ' '; dbg_out(T...); }
template<typename T> void mins(T& x, T y) {x = min(x, y);}
template<typename T> void maxs(T& x, T y) {x = max(x, y);}
template<typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using omset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;


int valid(int n, int inputSeq[]) { 
    set<int> st;
    int mini = 0;
    for (int i = 0; i < n; i++) {
        st.insert(inputSeq[i]);
        if (inputSeq[i] < inputSeq[mini]) 
            mini = i;
    }
    if (n != (int) st.size()) return 0;
    if (inputSeq[mini] > n) return 1;
    for (int i = 0; i < n; i++) {
        int pos = (mini + i) % n;
        if (inputSeq[pos] > n) continue;
        if (inputSeq[pos] != inputSeq[mini] + i) return 0;
    }
    return 1;
}

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
    int mini = 0;
    for (int i = 0; i < n; i++) {
        if (gondolaSeq[i] < gondolaSeq[mini]) 
            mini = i;
    }
    int val = gondolaSeq[mini];
    if (val > n) mini = 0, val = 1;
    vector<pi> ar(n);
    for (int i = 0; i < n; i++) {
        int pos = (mini + i) % n;
        ar[pos] = {gondolaSeq[pos], val};
        val++; if (val > n) val = 1;
    }
    sort(all(ar));
    int pp = 0;
    int z = n + 1;
    for (int i = 0; i < n; i++) {
        if (ar[i].ft <= n) continue;
        int cur = ar[i].sd;
        while (cur < ar[i].ft) {
            replacementSeq[pp++] = cur;
            cur = z++;
        }
    }
    return pp;
}

ll bp(ll a, ll n) {
    if (n == 0) return 1ll;
    if (n & 1) return a * bp(a, n - 1) % MOD;
    ll h = bp(a, n / 2);
    return h * h % MOD;
}

int countReplacement(int n, int inputSeq[]) {
    if (!valid(n, inputSeq)) return 0;
    int bad = 0;
    for (int i = 0; i < n; i++) {
        if (inputSeq[i] > n) bad++;
    }
    sort(inputSeq, inputSeq + n);
    ll ans = (bad == n ? n : 1); int cur = n + 1;
    for (int i = 0; i < n; i++) {
        if (inputSeq[i] <= n) continue;
        int k = inputSeq[i] - cur;
        (ans *= bp(bad, k)) %= MOD;
        cur = inputSeq[i] + 1;
        bad--;
    }
    return ans;
}

Subtask #1
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 #2
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
6 Correct 11 ms 2132 KB Output is correct
7 Correct 48 ms 3604 KB Output is correct
8 Correct 24 ms 3884 KB Output is correct
9 Correct 7 ms 1468 KB Output is correct
10 Correct 32 ms 4400 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 1 ms 212 KB Output is correct
6 Correct 14 ms 2132 KB Output is correct
7 Correct 26 ms 3564 KB Output is correct
8 Correct 20 ms 3924 KB Output is correct
9 Correct 7 ms 1364 KB Output is correct
10 Correct 25 ms 4420 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 13 ms 2092 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 42 ms 4560 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 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 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 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

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 1 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 2 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 13 ms 1236 KB Output is correct
12 Correct 11 ms 1364 KB Output is correct
13 Correct 14 ms 1092 KB Output is correct
14 Correct 9 ms 1136 KB Output is correct
15 Correct 18 ms 2000 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 1 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 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 0 ms 212 KB Output is correct

Subtask #9
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 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 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 34 ms 4024 KB Output is correct
10 Correct 34 ms 3348 KB Output is correct
11 Correct 13 ms 1364 KB Output is correct
12 Correct 12 ms 1620 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 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 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 34 ms 3948 KB Output is correct
10 Correct 26 ms 3412 KB Output is correct
11 Correct 9 ms 1364 KB Output is correct
12 Correct 14 ms 1620 KB Output is correct
13 Correct 3 ms 596 KB Output is correct
14 Correct 45 ms 5308 KB Output is correct
15 Correct 54 ms 6020 KB Output is correct
16 Correct 7 ms 1280 KB Output is correct
17 Correct 33 ms 4144 KB Output is correct
18 Correct 16 ms 2388 KB Output is correct