oj.uz

Submission #242447

# Submission time Handle Problem Language Result Execution time Memory
242447 2020-06-27T17:19:12 Z joseacaz Gondola (IOI14_gondola) C++17
100 / 100
 49 ms 6352 KB 
#include "gondola.h"
#include <bits/stdc++.h>

#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

const int MAXN = 1e6 + 5;
vi input;
unordered_map<int, int> vis;

int valid(int N, int inputSeq[])
{
    input.clear();
    for(int i = 0; i < N; i++)
        input.pb(inputSeq[i]);
    
    int ans = 0, one = 0;
    vis.clear();
    for(int i = 0; i < N; i++)
    {
        if(vis[input[i]])
            return 0;
        vis[input[i]]++;
    }
    for(int i = 0; i < N; i++)
    {
        if(input[i] <= N)
        {
            one = 1;
            int idx;
            for(int j = 0; j < N; j++)
            {
                idx = (i + (j + 1 - input[i]) + N) % N;
                if(input[idx] == j + 1 || input[idx] > N)
                    ans++;
            }
            break;
        }
    }
    
    if(!one)
        return 1;
    return (ans == N);
}

int replacement(int N, int gondolaSeq[], int replacementSeq[])
{
    input.clear();
    for(int i = 0; i < N; i++)
        input.pb(gondolaSeq[i]);
    
    int one = 0;
    for(int i = 0; i < N; i++)
        if(input[i] <= N)
            one = (i - input[i] + 1 + N) % N;
    
    vpi seq;
    for(int i = 0; i < N; i++)
        seq.pb({input[(one + i) % N], i + 1});
    sort(all(seq));
    int curr = 0, newGondola = N + 1;
    for(int i = 0; i < N; i++)
    {
        while(seq[i].second != seq[i].first)
        {
            replacementSeq[curr++] = seq[i].second;
            seq[i].second = newGondola++;
        }
    }
    return curr;
}

const ll MOD = 1e9 + 9;

ll binexp(ll b, ll e)
{
    if(e == 0)  return 1;
    if(e&1) return (b * binexp(b, e-1)) % MOD;
    else
    {
        ll aux = binexp(b, e/2);
        return (aux*aux) % MOD;
    }
}

int countReplacement(int N, int inputSeq[])
{
    if(!valid(N, inputSeq))
        return 0;
    
    int one = -1;
    for(int i = 0; i < N; i++)
        if(input[i] <= N)
            one = (i - input[i] + 1 + N) % N;
    
    vpi seq;
    for(int i = 0; i < N; i++)
        seq.pb({input[(max(one, 0) + i) % N], i + 1});
    sort(all(seq));
    
    int last = N;
    ll ans = 1;
    for(int i = 0; i < N; i++)
    {
        if(seq[i].first <= N)
            continue;
        ans *= binexp(N - i, seq[i].first - last - 1);
        last = seq[i].first;
        ans %= MOD;
    }
    if(one < 0)
        ans = (ans * N) % MOD;
    return ans;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 4 ms 256 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 16 ms 2220 KB Output is correct
7 Correct 17 ms 1276 KB Output is correct
8 Correct 22 ms 3928 KB Output is correct
9 Correct 11 ms 1408 KB Output is correct
10 Correct 24 ms 4440 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 13 ms 2220 KB Output is correct
7 Correct 18 ms 1404 KB Output is correct
8 Correct 21 ms 4056 KB Output is correct
9 Correct 10 ms 1408 KB Output is correct
10 Correct 24 ms 4440 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 4 ms 256 KB Output is correct
13 Correct 15 ms 2092 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 29 ms 4560 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 19 ms 2168 KB Output is correct
12 Correct 21 ms 2168 KB Output is correct
13 Correct 21 ms 1512 KB Output is correct
14 Correct 20 ms 2040 KB Output is correct
15 Correct 25 ms 2296 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 36 ms 5584 KB Output is correct
10 Correct 32 ms 4620 KB Output is correct
11 Correct 14 ms 1792 KB Output is correct
12 Correct 16 ms 2224 KB Output is correct
13 Correct 7 ms 896 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 36 ms 5592 KB Output is correct
10 Correct 30 ms 4492 KB Output is correct
11 Correct 13 ms 1792 KB Output is correct
12 Correct 16 ms 2352 KB Output is correct
13 Correct 7 ms 768 KB Output is correct
14 Correct 42 ms 5968 KB Output is correct
15 Correct 49 ms 6352 KB Output is correct
16 Correct 13 ms 1792 KB Output is correct
17 Correct 34 ms 5252 KB Output is correct
18 Correct 21 ms 3292 KB Output is correct