oj.uz

Submission #66369

# Submission time Handle Problem Language Result Execution time Memory
66369 2018-08-10T10:30:55 Z someone_aa Gondola (IOI14_gondola) C++17
90 / 100
 42 ms 11576 KB 
#include "gondola.h"
#include <bits/stdc++.h>

#define ll long long
using namespace std;
const int maxn = 250100;
const ll mod = 1000000009;
bool exist[maxn];
int fin_val[maxn];
ll cnt[maxn];

int valid(int n, int arr[]) {
    bool check = true;

    for(int i=1;i<n;i++) {
        if(arr[i] > n) continue;
        else if(arr[i] == 1) {
            if(arr[i-1] < n)
                check = false;
        }
        else {
            if(arr[i-1] <= n && arr[i-1] != arr[i] - 1) check = false;
        }
    }

    sort(arr, arr+n);
    for(int i=1;i<n;i++) {
        if(arr[i] == arr[i-1]) check = false;
    }
    if(check) return 1;
    else return 0;
}

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

int replacement(int n, int arr[], int replacementSeq[]) {
    int maxm = 0;
    int found_i = 0, st_val = 1;
    for(int i=0;i<n;i++) {
        exist[arr[i]] = true;
        if(arr[i] <= n) {
            found_i = i;
            st_val = arr[i];
        }
        maxm = max(maxm, arr[i]);
    }
    exist[n] = true;
    int l = maxm - n;


    for(int i=found_i;i<n;i++) {
        fin_val[i] = st_val;
        st_val++;
        if(st_val == n + 1) st_val = 1;
    }

    for(int i=0;i<found_i;i++) {
        fin_val[i] = st_val;
        st_val++;
        if(st_val == n + 1) st_val = 1;
    }

    for(int i=0;i<n;i++) {
        while(!exist[arr[i]-1] && arr[i] > n) {
            replacementSeq[arr[i]-n-1] = arr[i] - 1;
            arr[i]--;
        }
        if(arr[i] > n) replacementSeq[arr[i]-n-1] = fin_val[i];
    }

    return l;
}

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

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

    int minv = INT_MAX, maxv = 0;
    for(int i=0;i<n;i++) {
        minv = min(minv, arr[i]);
        maxv = max(maxv, arr[i]);
        exist[arr[i]] = true;
    }

    ll result = 1LL;
    for(int i=maxv;i>=n+1;i--) {
        cnt[i] = cnt[i+1];
        if(exist[i]) cnt[i]++;
    }
    for(int i=n+1;i<=maxv;i++) {
        if(!exist[i]) {
            result *= cnt[i];
            result %= mod;
        }
    }
    if(minv > n) {
        result *= n;
        result %= mod;
    }
    return result;
}

/*int main() {
    int arr[] = {2, 3, 4, 12, 6, 7, 1};
    int arr2[1];
    cout<<countReplacement(7, arr);
}*/

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 496 KB Output is correct
2 Correct 4 ms 544 KB Output is correct
3 Correct 3 ms 584 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 16 ms 1008 KB Output is correct
7 Correct 23 ms 1672 KB Output is correct
8 Correct 17 ms 1976 KB Output is correct
9 Correct 7 ms 1976 KB Output is correct
10 Correct 22 ms 2636 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 3 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 17 ms 2656 KB Output is correct
7 Correct 24 ms 3384 KB Output is correct
8 Correct 24 ms 3760 KB Output is correct
9 Correct 7 ms 3760 KB Output is correct
10 Correct 20 ms 4412 KB Output is correct
11 Correct 3 ms 4412 KB Output is correct
12 Correct 3 ms 4412 KB Output is correct
13 Correct 12 ms 4412 KB Output is correct
14 Correct 3 ms 4412 KB Output is correct
15 Correct 42 ms 5160 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5160 KB Output is correct
2 Correct 2 ms 5160 KB Output is correct
3 Correct 2 ms 5160 KB Output is correct
4 Correct 3 ms 5160 KB Output is correct
5 Correct 3 ms 5160 KB Output is correct
6 Correct 2 ms 5160 KB Output is correct
7 Correct 3 ms 5160 KB Output is correct
8 Correct 2 ms 5160 KB Output is correct
9 Correct 4 ms 5160 KB Output is correct
10 Correct 3 ms 5160 KB Output is correct
11 Correct 16 ms 6188 KB Output is correct
12 Correct 17 ms 6764 KB Output is correct
13 Correct 20 ms 7232 KB Output is correct
14 Correct 15 ms 7308 KB Output is correct
15 Correct 23 ms 8780 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8780 KB Output is correct
2 Correct 2 ms 8780 KB Output is correct
3 Correct 3 ms 8780 KB Output is correct
4 Correct 3 ms 8780 KB Output is correct
5 Correct 3 ms 8780 KB Output is correct
6 Correct 3 ms 8780 KB Output is correct
7 Correct 3 ms 8780 KB Output is correct
8 Correct 3 ms 8780 KB Output is correct
9 Correct 21 ms 8920 KB Output is correct
10 Correct 17 ms 8920 KB Output is correct
11 Correct 12 ms 9940 KB Output is correct
12 Correct 10 ms 9940 KB Output is correct
13 Correct 7 ms 10140 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10140 KB Output is correct
2 Correct 3 ms 10140 KB Output is correct
3 Correct 2 ms 10140 KB Output is correct
4 Correct 3 ms 10140 KB Output is correct
5 Correct 2 ms 10140 KB Output is correct
6 Correct 2 ms 10140 KB Output is correct
7 Correct 2 ms 10140 KB Output is correct
8 Correct 3 ms 10140 KB Output is correct
9 Correct 29 ms 10352 KB Output is correct
10 Correct 18 ms 10352 KB Output is correct
11 Correct 15 ms 11396 KB Output is correct
12 Correct 14 ms 11396 KB Output is correct
13 Correct 8 ms 11576 KB Output is correct
14 Runtime error 26 ms 11576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -