oj.uz

Submission #66577

# Submission time Handle Problem Language Result Execution time Memory
66577 2018-08-11T13:58:04 Z aquablitz11 Gondola (IOI14_gondola) C++14
100 / 100
 96 ms 6512 KB 
#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;

int valid(int n, int A[])
{
    set<int> seen;
    int six = -1;
    for (int i = 0; i < n; ++i) {
        if (seen.count(A[i])) return 0;
        seen.insert(A[i]);
        if (A[i] <= n) six = (i-(A[i]-1)+n)%n;
    }
    if (six == -1) return 1;
    for (int i = 0; i < n; ++i) {
        int j = (six+i)%n;
        if (A[j] <= n && A[j] != i+1)
            return false;
    }

    return 1;
}

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

int replacement(int n, int A[], int ret[])
{
    int six = 0;
    for (int i = 0; i < n; ++i) {
        if (A[i] <= n) six = (i-(A[i]-1)+n)%n;
    }
    map<int, int> num;
    for (int i = 0; i < n; ++i) {
        int j = (six+i)%n;
        if (A[j] > n)
            num[A[j]] = i+1;
    }
    int cnt = 0, v = n;
    for (auto p : num) {
        int x = p.second, y = p.first;
        while (x < y) {
            ret[cnt++] = x;
            x = ++v;
        }
    }

    return cnt;
}

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

const int MOD = 1e9+9;
static inline int mul(int a, int b) { return (a*1ll*b)%MOD; }
static inline int modpow(int a, int b) {
    int ans = 1;
    while (b) {
        if (b&1) ans = mul(ans, a);
        a = mul(a, a);
        b >>= 1;
    }
    return ans;
}
int countReplacement(int n, int A[])
{
    if (!valid(n, A)) return 0;
    int six = -1;
    vector<int> big;
    for (int i = 0; i < n; ++i) {
        if (A[i] <= n) six = (i-(A[i]-1)+n)%n;
        else big.push_back(A[i]);
    }
    sort(big.begin(), big.end(), greater<int>());
    int ans = six == -1 ? n : 1;
    int prev = n;
    while (!big.empty()) {
        int x = big.back();
        big.pop_back();
        ans = mul(ans, modpow(big.size()+1, x-prev-1));
        prev = x;
    }

    return ans;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 556 KB Output is correct
2 Correct 2 ms 564 KB Output is correct
3 Correct 2 ms 564 KB Output is correct
4 Correct 2 ms 564 KB Output is correct
5 Correct 2 ms 564 KB Output is correct
6 Correct 19 ms 2364 KB Output is correct
7 Correct 14 ms 2364 KB Output is correct
8 Correct 35 ms 4108 KB Output is correct
9 Correct 12 ms 4108 KB Output is correct
10 Correct 46 ms 4756 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4756 KB Output is correct
2 Correct 2 ms 4756 KB Output is correct
3 Correct 2 ms 4756 KB Output is correct
4 Correct 2 ms 4756 KB Output is correct
5 Correct 2 ms 4756 KB Output is correct
6 Correct 20 ms 4756 KB Output is correct
7 Correct 14 ms 4756 KB Output is correct
8 Correct 34 ms 4756 KB Output is correct
9 Correct 11 ms 4756 KB Output is correct
10 Correct 61 ms 4860 KB Output is correct
11 Correct 3 ms 4860 KB Output is correct
12 Correct 3 ms 4860 KB Output is correct
13 Correct 26 ms 4860 KB Output is correct
14 Correct 2 ms 4860 KB Output is correct
15 Correct 66 ms 4988 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4988 KB Output is correct
2 Correct 2 ms 4988 KB Output is correct
3 Correct 2 ms 4988 KB Output is correct
4 Correct 2 ms 4988 KB Output is correct
5 Correct 2 ms 4988 KB Output is correct
6 Correct 2 ms 4988 KB Output is correct
7 Correct 2 ms 4988 KB Output is correct
8 Correct 2 ms 4988 KB Output is correct
9 Correct 3 ms 4988 KB Output is correct
10 Correct 3 ms 4988 KB Output is correct
11 Correct 17 ms 4988 KB Output is correct
12 Correct 14 ms 4988 KB Output is correct
13 Correct 29 ms 4988 KB Output is correct
14 Correct 16 ms 4988 KB Output is correct
15 Correct 28 ms 4988 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4988 KB Output is correct
2 Correct 2 ms 4988 KB Output is correct
3 Correct 2 ms 4988 KB Output is correct
4 Correct 2 ms 4988 KB Output is correct
5 Correct 3 ms 4988 KB Output is correct
6 Correct 2 ms 4988 KB Output is correct
7 Correct 2 ms 4988 KB Output is correct
8 Correct 3 ms 4988 KB Output is correct
9 Correct 60 ms 4988 KB Output is correct
10 Correct 63 ms 4988 KB Output is correct
11 Correct 17 ms 4988 KB Output is correct
12 Correct 21 ms 4988 KB Output is correct
13 Correct 6 ms 4988 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4988 KB Output is correct
2 Correct 2 ms 4988 KB Output is correct
3 Correct 3 ms 4988 KB Output is correct
4 Correct 2 ms 4988 KB Output is correct
5 Correct 3 ms 4988 KB Output is correct
6 Correct 2 ms 4988 KB Output is correct
7 Correct 2 ms 4988 KB Output is correct
8 Correct 2 ms 4988 KB Output is correct
9 Correct 63 ms 4988 KB Output is correct
10 Correct 49 ms 4988 KB Output is correct
11 Correct 18 ms 4988 KB Output is correct
12 Correct 21 ms 4988 KB Output is correct
13 Correct 6 ms 4988 KB Output is correct
14 Correct 79 ms 4988 KB Output is correct
15 Correct 96 ms 6512 KB Output is correct
16 Correct 15 ms 6512 KB Output is correct
17 Correct 58 ms 6512 KB Output is correct
18 Correct 30 ms 6512 KB Output is correct