oj.uz

Submission #103769

# Submission time Handle Problem Language Result Execution time Memory
103769 2019-04-02T13:21:27 Z SecretAgent007 Gondola (IOI14_gondola) C++17
90 / 100
 1000 ms 263168 KB 
#include "gondola.h"
#include <bits/stdc++.h>

using namespace std;

int valid(int n, int inputSeq[]){

    int index = 0;
    int num = n;

    map< int, bool> visited;

    for(int i = 0; i < n; i++){
        if(visited[inputSeq[i]]) return 0;
        visited[inputSeq[i]] = true;
        if(inputSeq[i] <= num){
            num = inputSeq[i];
            index = i;
        }
    }

    int start = (index-num+1+n)%n;

    int curr = 1;

    for(int i = start; i < n; i++){
        if(inputSeq[i] <= n && inputSeq[i] != curr) return 0;
        curr++;
    }
    for(int j = 0; j < start; j++){
        if(inputSeq[j] <= n && inputSeq[j] != curr) return 0;
        curr++;
    }
    return 1;
}

int replacement(int n, int gondolaSeq[], int replacementSeq[]){
    int index = 0;
    int num = n;

    int maxi = 0;

    for(int i = 0; i < n; i++){
        if(gondolaSeq[i] <= num){
            num = gondolaSeq[i];
            index = i;
        }
        maxi = max(maxi, gondolaSeq[i]);
    }

    int start = (index-num+1+n)%n;

    if(gondolaSeq[index] > n) start = 0;

    int curr = 1;

    map<int, int> mape;

    vector< int > current(n+1);

    for(int i = 1; i <= n; i++){
        current[i] = i;
    }

    int in;

    for(int i = start; i < n; i++){
        mape[gondolaSeq[i]] = curr;
        if(gondolaSeq[i] == maxi) in = curr;
        curr++;
    }
    for(int j = 0; j < start; j++){
        mape[gondolaSeq[j]] = curr;
        if(gondolaSeq[j] == maxi) in = curr;
        curr++;
    }

    int c = 0;

    for(int i = n+1; i <= maxi; i++){
        if(mape[i] != 0){
            replacementSeq[c] = current[mape[i]];
            current[mape[i]] = i;
        }else{
            replacementSeq[c] = current[in];
            current[in] = i;
        }
        c++;
    }

    return c;
}

int last;

map<int, bool> visited;
vector< int > ve;
vector< int > cnt;

const int mod = 1e9+9;

int dp(int curr, int n){
    if(curr >= last){
        return 1;
    }

    if(visited[curr]){
        return dp(curr+1,n);
    }

    long long  index = n-(lower_bound(cnt.begin(), cnt.end(), curr+1)-cnt.begin());
    long long nb = index;
    nb = nb%mod;

    long long tempo = (nb*dp(curr+1,n))%mod;
    return (tempo);
}

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

    ve.resize(n);
    cnt.resize(n);

    int mini = mod;

    for(int i = 0; i < n; i++){
        mini = min(mini, inputSeq[i]);
        last = max(last, inputSeq[i]);
        ve[i] = inputSeq[i];
        cnt[i] = inputSeq[i];
        visited[inputSeq[i]] = true;
    }

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

    if(mini >= n){
        long long rep = dp(n+1,n);
        long long ans = ((long long)n*rep)%mod;
        return ans;
    }

    return dp(n+1, n);
}
/*
int main(){
    int n;
    cin >> n;
    int v[n];
    int maxi = 0;
    for(int i = 0; i < n; i++){
        cin >> v[i];
        maxi = max(maxi, v[i]);
    }
    int ans[maxi-n];
    cout << replacement(n,v,ans) << endl;
    for(int a : ans){
        cout << a << ' ';
    }
    cout << endl;

    cout << "NUMBER " << countReplacement(n,v) << endl;
}
*/

Compilation message

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:85:43: warning: 'in' may be used uninitialized in this function [-Wmaybe-uninitialized]
             replacementSeq[c] = current[in];
                                           ^

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 19 ms 2304 KB Output is correct
7 Correct 16 ms 768 KB Output is correct
8 Correct 32 ms 4088 KB Output is correct
9 Correct 14 ms 1536 KB Output is correct
10 Correct 50 ms 4728 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 17 ms 2176 KB Output is correct
7 Correct 15 ms 768 KB Output is correct
8 Correct 31 ms 3960 KB Output is correct
9 Correct 10 ms 1536 KB Output is correct
10 Correct 41 ms 4600 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 26 ms 2168 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 73 ms 4728 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 3 ms 304 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 412 KB Output is correct
8 Correct 4 ms 640 KB Output is correct
9 Correct 3 ms 484 KB Output is correct
10 Correct 4 ms 640 KB Output is correct
11 Correct 31 ms 4736 KB Output is correct
12 Correct 44 ms 5240 KB Output is correct
13 Correct 61 ms 4708 KB Output is correct
14 Correct 34 ms 4600 KB Output is correct
15 Correct 97 ms 10288 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 256 KB Output is correct
9 Correct 125 ms 15964 KB Output is correct
10 Correct 104 ms 11256 KB Output is correct
11 Correct 94 ms 26104 KB Output is correct
12 Correct 61 ms 13012 KB Output is correct
13 Correct 100 ms 27128 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 141 ms 15992 KB Output is correct
10 Correct 116 ms 11192 KB Output is correct
11 Correct 88 ms 26104 KB Output is correct
12 Correct 66 ms 12920 KB Output is correct
13 Correct 88 ms 27256 KB Output is correct
14 Runtime error 1006 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -