oj.uz

Submission #195625

# Submission time Handle Problem Language Result Execution time Memory
195625 2020-01-16T16:18:41 Z jovan_b Gondola (IOI14_gondola) C++17
100 / 100
 106 ms 10448 KB 
#include "gondola.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll niz[100005];
ll niz1[100005];
map <ll, bool> bio;

const int MOD = 1000000009;

ll mul(ll a, ll b){
    return (a*b)%MOD;
}

int pw(int a, int b){
    if(b == 0) return 1;
    int res = pw(a, b/2);
    res = mul(res, res);
    if(b%2) res = mul(res, a);
    return res;
}

void shiftuj(int n, int k){
    for(int i=1; i<=n; i++) niz1[i] = niz[i];
    if(k < 0) k += n;
    for(int i=k+1; i<=n; i++){
        niz[i] = niz1[i-k];
    }
    for(int i=1; i<=k; i++){
        niz[i] = niz1[n-k+i];
    }
}

int valid(int n, int inputSeq[]){
    for(int i=1; i<=n; i++){
        niz[i] = inputSeq[i-1];
    }
    for(int i=1; i<=n; i++){
        if(niz[i] <= n){
            shiftuj(n, niz[i]-i);
            break;
        }
    }
    for(int i=1; i<=n; i++){
        if(niz[i] <= n && niz[i] != i) return 0;
        if(bio[niz[i]]) return 0;
        bio[niz[i]] = 1;
    }
    return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[]){
    for(int i=1; i<=n; i++) niz[i] = gondolaSeq[i-1];
    for(int i=1; i<=n; i++){
        if(niz[i] <= n){
            shiftuj(n, niz[i]-i);
            break;
        }
    }
    vector <pair <int, int>> vec;
    for(int i=1; i<=n; i++){
        if(niz[i] != i){
            vec.push_back({niz[i], i});
        }
    }
    sort(vec.begin(), vec.end());
    int prosli = n+1;
    int l = 0;
    for(auto par : vec){
        int a = par.first;
        int b = par.second;
        replacementSeq[l++] = b;
        while(prosli < a){
            replacementSeq[l++] = prosli;
            prosli++;
        }
        prosli++;
    }
    return l;
}

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

int countReplacement(int n, int inputSeq[]){
    if(!valid(n, inputSeq)) return 0;
    vector <pair <ll, ll>> vec;
    for(ll i=1; i<=n; i++){
        if(niz[i] != i){
            vec.push_back({niz[i], i});
        }
    }
    sort(vec.begin(), vec.end());
    ll prosli = n+1;
    ll g = vec.size();
    ll sol = 1;
    for(auto par : vec){
        ll a = par.first;
        ll b = par.second;
        sol = mul(sol, pw(g, max(0LL, a-prosli)));
        prosli = a+1;
        g--;
    }
    if(vec.size() == n) sol = mul(sol, n);
    return sol;
}

Compilation message

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:103:12: warning: unused variable 'b' [-Wunused-variable]
         ll b = par.second;
            ^
gondola.cpp:108:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(vec.size() == n) sol = mul(sol, n);
        ~~~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 0 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 27 ms 3576 KB Output is correct
7 Correct 16 ms 2552 KB Output is correct
8 Correct 52 ms 6688 KB Output is correct
9 Correct 14 ms 2296 KB Output is correct
10 Correct 61 ms 7672 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 404 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 24 ms 3644 KB Output is correct
7 Correct 16 ms 2472 KB Output is correct
8 Correct 47 ms 6648 KB Output is correct
9 Correct 14 ms 2296 KB Output is correct
10 Correct 52 ms 7672 KB Output is correct
11 Correct 6 ms 248 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 8 ms 1244 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 17 ms 2516 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 404 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 400 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 296 KB Output is correct
6 Correct 2 ms 360 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 2 ms 420 KB Output is correct
10 Correct 3 ms 376 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 292 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 388 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 368 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 0 ms 368 KB Output is correct
10 Correct 3 ms 372 KB Output is correct
11 Correct 13 ms 2304 KB Output is correct
12 Correct 15 ms 2600 KB Output is correct
13 Correct 18 ms 2016 KB Output is correct
14 Correct 10 ms 2248 KB Output is correct
15 Correct 24 ms 2604 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 376 KB Output is correct
2 Correct 2 ms 404 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 348 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 296 KB Output is correct
2 Correct 2 ms 408 KB Output is correct
3 Correct 2 ms 396 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 372 KB Output is correct
7 Correct 4 ms 400 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 72 ms 7996 KB Output is correct
10 Correct 56 ms 6884 KB Output is correct
11 Correct 20 ms 2944 KB Output is correct
12 Correct 26 ms 3360 KB Output is correct
13 Correct 3 ms 1064 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 65 ms 8032 KB Output is correct
10 Correct 51 ms 6948 KB Output is correct
11 Correct 23 ms 2924 KB Output is correct
12 Correct 22 ms 3440 KB Output is correct
13 Correct 5 ms 1144 KB Output is correct
14 Correct 101 ms 9540 KB Output is correct
15 Correct 106 ms 10448 KB Output is correct
16 Correct 16 ms 2424 KB Output is correct
17 Correct 66 ms 6868 KB Output is correct
18 Correct 36 ms 4464 KB Output is correct