oj.uz

Submission #582284

# Submission time Handle Problem Language Result Execution time Memory
582284 2022-06-23T15:32:12 Z kamelfanger83 Gondola (IOI14_gondola) C++14
100 / 100
 95 ms 6476 KB 
#include <iostream>
#include <vector>
#include "gondola.h"
#include <limits>
#include <numeric>
#include <algorithm>
#include <map>

#define int long long

using namespace std;

int mode = 1e9+9;

signed valid(signed n, signed inputSeq[]){
    int one = numeric_limits<int>::min();
    map<int, bool> used;
    for(int c = 0; c < n; c++){
        if(inputSeq[c] <= n){
            if(one == numeric_limits<int>::min()) one = c - inputSeq[c] + 1;
            if((c - one + 1) % n != inputSeq[c] % n) return 0; 
        }
        else{
            if(used[inputSeq[c]]) return 0;
            used[inputSeq[c]] = true;
        }
    }
    return 1;
}

signed replacement(signed n, signed gondolaSeq[], signed replacementSeq[]){
    int one = 0;
    for(int c = 0; c < n; c++){
        if(gondolaSeq[c] <= n) one = c - gondolaSeq[c] + 1;
    }

    vector<int> ind (n); iota(ind.begin(), ind.end(), 0);
    auto gcomp = [&](int u, int v){return gondolaSeq[u] < gondolaSeq[v];};
    sort(ind.begin(), ind.end(), gcomp);

    int repg = n;
    int l = 0;
    vector<int> ac (n); 
    for(int acer = 0; acer < n; acer++){
        int num = (acer - one + 1 + n) % n;
        if(num == 0) num = n;
        ac[acer] = num;
    }
    for(int rep : ind){
        while(repg < gondolaSeq[rep]){
            replacementSeq[l++] = ac[rep];
            repg++;
            ac[rep] = repg;
        }
    }
    return l;
}

int fastpow(long long b, long long e){
    long long res = 1;
    for(;e != 0;e>>=1){
        if(e&1) res *= b;
        res %= mode;
        b *= b;
        b %= mode;
    }
    return res;
}

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

    int defs = 0;

    for(int c = 0; c < n; c++) if(inputSeq[c] <= n) defs++;

    vector<int> ind (n); iota(ind.begin(), ind.end(), 0);
    auto gcomp = [&](int u, int v){return inputSeq[u] < inputSeq[v];};
    sort(ind.begin(), ind.end(), gcomp);

    int repg = n;
    int p = 1;
    for(int ig = 0; ig < n; ig++){
        if(repg < inputSeq[ind[ig]] - 1){
            p *= fastpow(n-ig,inputSeq[ind[ig]] - repg - 1);
            p %= mode;
        }
        if(inputSeq[ind[ig]] > n) repg = inputSeq[ind[ig]];
    }

    if(defs == 0){
        p *= n; p %= mode;
    }

    return p;
}

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 304 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 304 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 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 4 ms 468 KB Output is correct
7 Correct 9 ms 764 KB Output is correct
8 Correct 9 ms 716 KB Output is correct
9 Correct 4 ms 448 KB Output is correct
10 Correct 8 ms 872 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 308 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 6 ms 468 KB Output is correct
7 Correct 14 ms 724 KB Output is correct
8 Correct 8 ms 620 KB Output is correct
9 Correct 3 ms 444 KB Output is correct
10 Correct 11 ms 724 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 4 ms 476 KB Output is correct
14 Correct 1 ms 312 KB Output is correct
15 Correct 10 ms 788 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 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 #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 312 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 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 304 KB Output is correct
9 Correct 1 ms 304 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 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
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 312 KB Output is correct
11 Correct 13 ms 1808 KB Output is correct
12 Correct 13 ms 2076 KB Output is correct
13 Correct 13 ms 1236 KB Output is correct
14 Correct 10 ms 1816 KB Output is correct
15 Correct 19 ms 2120 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 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 300 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 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 1 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 45 ms 4168 KB Output is correct
10 Correct 27 ms 3276 KB Output is correct
11 Correct 13 ms 1948 KB Output is correct
12 Correct 14 ms 2028 KB Output is correct
13 Correct 4 ms 724 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 1 ms 304 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 1 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 42 ms 4112 KB Output is correct
10 Correct 31 ms 3168 KB Output is correct
11 Correct 13 ms 1816 KB Output is correct
12 Correct 19 ms 2108 KB Output is correct
13 Correct 5 ms 724 KB Output is correct
14 Correct 77 ms 5868 KB Output is correct
15 Correct 95 ms 6476 KB Output is correct
16 Correct 10 ms 1364 KB Output is correct
17 Correct 42 ms 4484 KB Output is correct
18 Correct 22 ms 2684 KB Output is correct