답안 #66369 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
66369	2018-08-10T10:30:55 Z	someone_aa	곤돌라 (IOI14_gondola)	C++17	90 / 100	42 ms	11576 KB

gondola

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #66369

Compilation message