oj.uz

Submission #27765

# Submission time Handle Problem Language Result Execution time Memory
27765 2017-07-14T03:19:41 Z zoomswk Gondola (IOI14_gondola) C++14
100 / 100
 109 ms 8680 KB 
#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;

map<int, int> occ;

int valid(int n, int inputSeq[]){
    for(int i=0; i<n; i++){
        inputSeq[i]--;
        if(occ[inputSeq[i]]) return 0;
        occ[inputSeq[i]] = 1;
    }
    int must = -1;
    for(int i=0; i<n; i++) if(inputSeq[i] < n) must = i;
    if(must == -1) return 1;
    for(int i=0; i<n; i++) if(inputSeq[i] < n && (inputSeq[i]+n+must-i)%n != inputSeq[must]) return 0;
    return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[]){
    int inputSeq[100005];
    for(int i=0; i<n; i++) gondolaSeq[i]--;
    int must = -1;
    for(int i=0; i<n; i++) if(gondolaSeq[i] < n) must = i;
    if(must == -1){
        for(int i=0; i<n; i++) inputSeq[i] = i;;
    } else{
        int cur = gondolaSeq[must];
        for(int i=must-1; i>=0; i--){
            cur--;
            if(cur < 0) cur += n;
            inputSeq[i] = cur;
        }
        cur = gondolaSeq[must];
        for(int i=must+1; i<n; i++){
            cur++;
            if(cur >= n) cur -= n;
            inputSeq[i] = cur;
        }
    }
    priority_queue<pair<int, int>> pq;
    for(int i=0; i<n; i++) if(gondolaSeq[i] >= n) pq.push({-gondolaSeq[i], i});
    int ptr = n-1;
    int sz = 0;
    while(!pq.empty()){
        int num = -pq.top().first;
        int pos = pq.top().second;
        pq.pop();
        while(ptr < num){
            replacementSeq[sz++] = inputSeq[pos]+1;
            inputSeq[pos] = ++ptr;
        }
    }
    return sz;
}

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

const int MOD = (1e9)+9;

long long poww(int base, int to){
    long long res = 1;
    long long cur = base;
    while(to){
        if(to&1) res *= cur, res %= MOD;
        cur *= cur;
        cur %= MOD;
        to >>= 1;
    }
    return res;
}

int countReplacement(int n, int inputSeq[]){
    if(!valid(n, inputSeq)) return 0;
    long long res = 1;
    priority_queue<int> pq;
    int cnt = 0;
    for(int i=0; i<n; i++) if(inputSeq[i] >= n){ pq.push(-inputSeq[i]); cnt++; }
    int ptr = n-1;
    if(cnt == n) res = n;
    while(!pq.empty()){
        int num = -pq.top();
        pq.pop();
        res *= poww(cnt, num-ptr-1);
        res %= MOD;
        cnt--;
        ptr = num;
    }
    return res;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3396 KB Output is correct
2 Correct 0 ms 3396 KB Output is correct
3 Correct 0 ms 3396 KB Output is correct
4 Correct 0 ms 3396 KB Output is correct
5 Correct 0 ms 3396 KB Output is correct
6 Correct 16 ms 5112 KB Output is correct
7 Correct 16 ms 3396 KB Output is correct
8 Correct 29 ms 6696 KB Output is correct
9 Correct 9 ms 4452 KB Output is correct
10 Correct 39 ms 7356 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3396 KB Output is correct
2 Correct 0 ms 3396 KB Output is correct
3 Correct 0 ms 3396 KB Output is correct
4 Correct 0 ms 3396 KB Output is correct
5 Correct 0 ms 3396 KB Output is correct
6 Correct 16 ms 5112 KB Output is correct
7 Correct 9 ms 3396 KB Output is correct
8 Correct 39 ms 6696 KB Output is correct
9 Correct 6 ms 4452 KB Output is correct
10 Correct 39 ms 7356 KB Output is correct
11 Correct 0 ms 3396 KB Output is correct
12 Correct 0 ms 3396 KB Output is correct
13 Correct 19 ms 5112 KB Output is correct
14 Correct 0 ms 3396 KB Output is correct
15 Correct 56 ms 7488 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3660 KB Output is correct
2 Correct 0 ms 3664 KB Output is correct
3 Correct 0 ms 3664 KB Output is correct
4 Correct 0 ms 3660 KB Output is correct
5 Correct 0 ms 3660 KB Output is correct
6 Correct 0 ms 3660 KB Output is correct
7 Correct 0 ms 3660 KB Output is correct
8 Correct 0 ms 3664 KB Output is correct
9 Correct 0 ms 3664 KB Output is correct
10 Correct 0 ms 3664 KB Output is correct
11 Correct 6 ms 3660 KB Output is correct
12 Correct 13 ms 3660 KB Output is correct
13 Correct 26 ms 4128 KB Output is correct
14 Correct 9 ms 3660 KB Output is correct
15 Correct 26 ms 4128 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3396 KB Output is correct
2 Correct 0 ms 3396 KB Output is correct
3 Correct 0 ms 3396 KB Output is correct
4 Correct 0 ms 3396 KB Output is correct
5 Correct 0 ms 3396 KB Output is correct
6 Correct 0 ms 3396 KB Output is correct
7 Correct 0 ms 3396 KB Output is correct
8 Correct 0 ms 3396 KB Output is correct
9 Correct 76 ms 7304 KB Output is correct
10 Correct 46 ms 6720 KB Output is correct
11 Correct 16 ms 4644 KB Output is correct
12 Correct 16 ms 4880 KB Output is correct
13 Correct 3 ms 3796 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3396 KB Output is correct
2 Correct 0 ms 3396 KB Output is correct
3 Correct 0 ms 3396 KB Output is correct
4 Correct 0 ms 3396 KB Output is correct
5 Correct 0 ms 3396 KB Output is correct
6 Correct 0 ms 3396 KB Output is correct
7 Correct 0 ms 3396 KB Output is correct
8 Correct 0 ms 3396 KB Output is correct
9 Correct 69 ms 7304 KB Output is correct
10 Correct 59 ms 6720 KB Output is correct
11 Correct 16 ms 4644 KB Output is correct
12 Correct 19 ms 4880 KB Output is correct
13 Correct 3 ms 3796 KB Output is correct
14 Correct 79 ms 8172 KB Output is correct
15 Correct 109 ms 8680 KB Output is correct
16 Correct 16 ms 4460 KB Output is correct
17 Correct 63 ms 6844 KB Output is correct
18 Correct 26 ms 5536 KB Output is correct