답안 #620486

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
620486	2022-08-03T06:25:41 Z	Genius3435	곤돌라 (IOI14_gondola)	C++17	100 / 100	71 ms	5912 KB

gondola

#include <bits/stdc++.h>
using namespace std;

#include "gondola.h"
 
constexpr int N = 100005;
constexpr int M = 250005;
constexpr int MOD = 1000000009;
 
int valid(int n, int a[]) {
    // Check that values \leq n are in order, and that there are no repeats
 
    set<int> contained;
    for (int i = 0; i < n; ++i) {
        if (contained.count(a[i])) return 0;
        contained.insert(a[i]);
    }
 
 
    int start_index = -1;
    for (int i = 0; i < n; ++i) {
        if (a[i] <= n) {
            int index = (a[i] - (i+1) + n) % n;
            if (start_index == -1) {
                start_index = index;
            } else if (start_index != index) {
                return 0;
            }
        }
    }
 
    return 1;
}
 
 
 
int replacement(int n, int a[], int b[]) {
    static int position[M];
    auto it = max_element(a, a+n);
    int m = *it, max_idx = it-a;
    for (int i = 1; i <= m; ++i) {
        position[i] = -1;
    }
    for (int i = 0; i < n; ++i) {
        position[a[i]] = i;
    }
 
 
    int start_index = -1;
    for (int i = 0; i < n; ++i) {
        if (a[i] <= n) {
            start_index = (a[i] - (i+1) + n) % n;
            break;
        }
    }
    if (start_index == -1) {
        start_index = 0;
    }
 
 
    int *currSeq = new int[n];
    for (int i = 0; i < n; ++i) {
        currSeq[i] = (start_index + i) % n + 1;
    }
 
    for (int i = n+1; i <= m; ++i) {
        if (position[i] == -1) {
            b[i-n-1] = currSeq[max_idx];
            currSeq[max_idx] = i;
        } else {
            b[i-n-1] = currSeq[position[i]];
            currSeq[position[i]] = i;
        }
    }
 
    delete[] currSeq;
 
    return m-n;
}
 
 
 
int pow(long long b, int e, int m) {
    long long p = 1;
    while (e) {
        if (e&1) p = p * b % m;
        e >>= 1, b = b * b % m;
    }
    return p;
}
 
int countReplacement(int n, int a[]) {
    if (!valid(n, a)) return 0;
 
    std::set<int> contained;
    for (int i = 0; i < n; ++i) {
        if (a[i] > n) {
            contained.insert(a[i]);
        }
    }
 
    int positions = contained.size();
    long long ans = positions<n ? 1 : n;
    int prv = n;
    for (const int i : contained) {
        // All values in the interval (prv, i) have positions spots they could go in
        ans = ans * pow(positions, i-prv-1, MOD) % MOD;
        prv = i;
        positions--;
    }
    return ans;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	308 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	308 KB	Output is correct
4	Correct	1 ms	308 KB	Output is correct
5	Correct	1 ms	304 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	308 KB	Output is correct
2	Correct	1 ms	256 KB	Output is correct
3	Correct	1 ms	304 KB	Output is correct
4	Correct	1 ms	308 KB	Output is correct
5	Correct	1 ms	304 KB	Output is correct
6	Correct	13 ms	2392 KB	Output is correct
7	Correct	9 ms	1148 KB	Output is correct
8	Correct	25 ms	4228 KB	Output is correct
9	Correct	9 ms	1604 KB	Output is correct
10	Correct	33 ms	5136 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	308 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	304 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	15 ms	2496 KB	Output is correct
7	Correct	11 ms	1188 KB	Output is correct
8	Correct	23 ms	4264 KB	Output is correct
9	Correct	9 ms	1500 KB	Output is correct
10	Correct	39 ms	4972 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	14 ms	2376 KB	Output is correct
14	Correct	1 ms	304 KB	Output is correct
15	Correct	37 ms	5152 KB	Output is correct

Subtask #4
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	308 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	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	340 KB	Output is correct
5	Correct	0 ms	308 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	308 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	2 ms	468 KB	Output is correct

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	308 KB	Output is correct
7	Correct	1 ms	308 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	9 ms	1624 KB	Output is correct
12	Correct	14 ms	1856 KB	Output is correct
13	Correct	10 ms	1736 KB	Output is correct
14	Correct	8 ms	1620 KB	Output is correct
15	Correct	16 ms	3028 KB	Output is correct

Subtask #7
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	308 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	312 KB	Output is correct

Subtask #8
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	308 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 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	0 ms	212 KB	Output is correct
8	Correct	0 ms	304 KB	Output is correct

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	308 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	308 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	308 KB	Output is correct
9	Correct	57 ms	4452 KB	Output is correct
10	Correct	40 ms	3732 KB	Output is correct
11	Correct	14 ms	1588 KB	Output is correct
12	Correct	17 ms	1876 KB	Output is correct
13	Correct	4 ms	608 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	308 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	0 ms	212 KB	Output is correct
9	Correct	53 ms	4508 KB	Output is correct
10	Correct	38 ms	3788 KB	Output is correct
11	Correct	13 ms	1524 KB	Output is correct
12	Correct	17 ms	1804 KB	Output is correct
13	Correct	6 ms	628 KB	Output is correct
14	Correct	71 ms	5304 KB	Output is correct
15	Correct	71 ms	5912 KB	Output is correct
16	Correct	10 ms	1364 KB	Output is correct
17	Correct	45 ms	4032 KB	Output is correct
18	Correct	27 ms	2368 KB	Output is correct

답안 #620486

Compilation message