oj.uz

Submission #675602

# Submission time Handle Problem Language Result Execution time Memory
675602 2022-12-27T13:52:53 Z benjaminkleyn Gondola (IOI14_gondola) C++17
100 / 100
 39 ms 6724 KB 
#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
typedef long long ll;

unordered_map<int,int> cnt;
int valid(int n, int inputSeq[])
{
    cnt.clear();
    for (int i = 0; i < n; i++)
    {
        cnt[inputSeq[i]]++;
        if (cnt[inputSeq[i]] > 1)
            return 0;
    }
    int startPos = -1;
    for (int i = 0; i < n; i++)
        if (inputSeq[i] <= n)
        {
            startPos = (i - inputSeq[i] + 1 + n) % n;
            break;
        }
    if (startPos == -1)
        return 1;
    for (int i = 0; i < n; i++)
        if (inputSeq[i] <= n && startPos != (i - inputSeq[i] + 1 + n) % n)
            return 0;
    return 1;
}

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    vector<pair<int,int>> r;
    int startPos = 0;
    for (int i = 0; i < n; i++)
        if (gondolaSeq[i] > n)
            r.push_back({gondolaSeq[i], i});
        else
            startPos = (i - gondolaSeq[i] + 1 + n) % n;

    sort(r.begin(), r.end());

    int l = 0;
    int cur_mx = n;
    for (auto [newval, idx] : r)
    {
        int oldval = 1 + (idx - startPos + n) % n;
        while (oldval != newval)
        {
            replacementSeq[l++] = oldval;
            oldval = ++cur_mx;
        }
    }

    return l;
}

const ll mod = 1000000009;
ll binpow(ll b, ll n)
{
    ll res = 1;
    for (; n; n >>= 1, b = b * b % mod)
        if (n & 1)
            res = res * b % mod;
    return res;
}

int countReplacement(int n, int inputSeq[])
{
    if (!valid(n, inputSeq))
        return 0;

    vector<int> r;
    ll res = n;
    for (int i = 0; i < n; i++)
        if (inputSeq[i] > n)
            r.push_back(inputSeq[i]);
        else
            res = 1;

    sort(r.begin(), r.end());
    int cur_mx = n;
    int cnt = r.size();
    for (int newval : r)
    {
        res = res * binpow(cnt--, newval - 1 - cur_mx) % mod;
        cur_mx = newval;
    }
    return res;
}

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 1 ms 212 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 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 6 ms 1968 KB Output is correct
7 Correct 8 ms 588 KB Output is correct
8 Correct 21 ms 3428 KB Output is correct
9 Correct 4 ms 1492 KB Output is correct
10 Correct 12 ms 3804 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 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 6 ms 1868 KB Output is correct
7 Correct 7 ms 596 KB Output is correct
8 Correct 11 ms 3428 KB Output is correct
9 Correct 4 ms 1492 KB Output is correct
10 Correct 12 ms 3812 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 7 ms 1840 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 16 ms 5220 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 0 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 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 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 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 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 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 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 352 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 9 ms 560 KB Output is correct
12 Correct 11 ms 596 KB Output is correct
13 Correct 13 ms 1220 KB Output is correct
14 Correct 7 ms 596 KB Output is correct
15 Correct 25 ms 2232 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 0 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 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 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 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
9 Correct 20 ms 3984 KB Output is correct
10 Correct 18 ms 3512 KB Output is correct
11 Correct 7 ms 1660 KB Output is correct
12 Correct 11 ms 1840 KB Output is correct
13 Correct 2 ms 580 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 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 0 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 0 ms 212 KB Output is correct
9 Correct 20 ms 4012 KB Output is correct
10 Correct 16 ms 3460 KB Output is correct
11 Correct 9 ms 1584 KB Output is correct
12 Correct 7 ms 1732 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 24 ms 5592 KB Output is correct
15 Correct 39 ms 6724 KB Output is correct
16 Correct 7 ms 1368 KB Output is correct
17 Correct 29 ms 4316 KB Output is correct
18 Correct 12 ms 2608 KB Output is correct