oj.uz

Submission #537096

# Submission time Handle Problem Language Result Execution time Memory
537096 2022-03-14T13:04:16 Z timreizin Gondola (IOI14_gondola) C++17
100 / 100
 48 ms 5532 KB 
#include "gondola.h"
#include <vector>
#include <algorithm>
#include <set>
#include <numeric>

using namespace std;

int valid(int n, int inputSeq[])
{
    vector<int> a(n);
    int d = 0;
    for (int i = 0; i < n; ++i) if (inputSeq[i] <= n) d = (i - inputSeq[i] + 1 + n) % n;
    for (int i = 0; i < n; ++i) a[(i - d + n) % n] = inputSeq[i] - 1;
    if (set<int>(a.begin(), a.end()).size() != n) return 0;
    for (int i = 0; i < n; ++i) if (a[i] < n && a[i] != i) return 0;
    return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    vector<int> a(n);
    int d = 0;
    for (int i = 0; i < n; ++i) if (gondolaSeq[i] <= n) d = (i - gondolaSeq[i] + 1 + n) % n;
    for (int i = 0; i < n; ++i) a[(i - d + n) % n] = gondolaSeq[i];
    vector<int> inds(n);
    iota(inds.begin(), inds.end(), 0);
    sort(inds.begin(), inds.end(), [&a](int l, int r){ return a[l] < a[r]; });
    int l = 0, next = n + 1;
    for (int i : inds)
    {
        if (a[i] < next) continue;
        replacementSeq[l++] = i + 1;
        for (; next < a[i]; ++next) replacementSeq[l++] = next;
        ++next;
    }
    return l;
}

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

using ll = long long;

const ll MOD = 1e9 + 9;

ll binPow(ll a, ll n)
{
    ll res = 1;
    while (n)
    {
        if (n & 1) res = (res * a) % MOD;
        a = (a * a) % MOD;
        n >>= 1;
    }
    return res;
}

int countReplacement(int n, int inputSeq[])
{
    if (!valid(n, inputSeq)) return 0;
    vector<int> inds(n);
    iota(inds.begin(), inds.end(), 0);
    sort(inds.begin(), inds.end(), [inputSeq](int l, int r){ return inputSeq[l] < inputSeq[r]; });
    ll last = n, counter = n, help = 0;
    ll res = 1;
    for (int i = 0; i < n; ++i) counter -= inputSeq[i] <= n;
    if (counter == n) res = n;
    for (int i : inds)
    {
        if (inputSeq[i] <= n) continue;
        ll d = inputSeq[i] - last;
        res = (res * binPow(counter, d - 1)) % MOD;
        last = inputSeq[i];
        --counter;
    }
    return res;
}

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:15:45: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   15 |     if (set<int>(a.begin(), a.end()).size() != n) return 0;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:66:31: warning: unused variable 'help' [-Wunused-variable]
   66 |     ll last = n, counter = n, help = 0;
      |                               ^~~~

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

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 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 9 ms 2260 KB Output is correct
7 Correct 25 ms 3916 KB Output is correct
8 Correct 13 ms 4180 KB Output is correct
9 Correct 5 ms 1548 KB Output is correct
10 Correct 16 ms 4792 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 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 8 ms 2260 KB Output is correct
7 Correct 29 ms 3964 KB Output is correct
8 Correct 16 ms 4092 KB Output is correct
9 Correct 4 ms 1492 KB Output is correct
10 Correct 16 ms 4864 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 12 ms 2232 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 31 ms 4900 KB Output is correct

Subtask #4
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 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 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 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 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 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 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 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 10 ms 1108 KB Output is correct
12 Correct 12 ms 1236 KB Output is correct
13 Correct 13 ms 1092 KB Output is correct
14 Correct 10 ms 1108 KB Output is correct
15 Correct 20 ms 2224 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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct

Subtask #8
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 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 0 ms 212 KB Output is correct
7 Correct 0 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 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 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 35 ms 4328 KB Output is correct
10 Correct 26 ms 3596 KB Output is correct
11 Correct 11 ms 1500 KB Output is correct
12 Correct 11 ms 1748 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 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 32 ms 4296 KB Output is correct
10 Correct 28 ms 3644 KB Output is correct
11 Correct 16 ms 1484 KB Output is correct
12 Correct 12 ms 1776 KB Output is correct
13 Correct 3 ms 596 KB Output is correct
14 Correct 42 ms 4804 KB Output is correct
15 Correct 48 ms 5532 KB Output is correct
16 Correct 7 ms 1236 KB Output is correct
17 Correct 30 ms 3720 KB Output is correct
18 Correct 16 ms 2132 KB Output is correct