답안 #66577 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
66577	2018-08-11T13:58:04 Z	aquablitz11	곤돌라 (IOI14_gondola)	C++14	100 / 100	96 ms	6512 KB

gondola

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

int valid(int n, int A[])
{
    set<int> seen;
    int six = -1;
    for (int i = 0; i < n; ++i) {
        if (seen.count(A[i])) return 0;
        seen.insert(A[i]);
        if (A[i] <= n) six = (i-(A[i]-1)+n)%n;
    }
    if (six == -1) return 1;
    for (int i = 0; i < n; ++i) {
        int j = (six+i)%n;
        if (A[j] <= n && A[j] != i+1)
            return false;
    }

    return 1;
}

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

int replacement(int n, int A[], int ret[])
{
    int six = 0;
    for (int i = 0; i < n; ++i) {
        if (A[i] <= n) six = (i-(A[i]-1)+n)%n;
    }
    map<int, int> num;
    for (int i = 0; i < n; ++i) {
        int j = (six+i)%n;
        if (A[j] > n)
            num[A[j]] = i+1;
    }
    int cnt = 0, v = n;
    for (auto p : num) {
        int x = p.second, y = p.first;
        while (x < y) {
            ret[cnt++] = x;
            x = ++v;
        }
    }

    return cnt;
}

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

const int MOD = 1e9+9;
static inline int mul(int a, int b) { return (a*1ll*b)%MOD; }
static inline int modpow(int a, int b) {
    int ans = 1;
    while (b) {
        if (b&1) ans = mul(ans, a);
        a = mul(a, a);
        b >>= 1;
    }
    return ans;
}
int countReplacement(int n, int A[])
{
    if (!valid(n, A)) return 0;
    int six = -1;
    vector<int> big;
    for (int i = 0; i < n; ++i) {
        if (A[i] <= n) six = (i-(A[i]-1)+n)%n;
        else big.push_back(A[i]);
    }
    sort(big.begin(), big.end(), greater<int>());
    int ans = six == -1 ? n : 1;
    int prev = n;
    while (!big.empty()) {
        int x = big.back();
        big.pop_back();
        ans = mul(ans, modpow(big.size()+1, x-prev-1));
        prev = x;
    }

    return ans;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	484 KB	Output is correct
3	Correct	2 ms	484 KB	Output is correct
4	Correct	2 ms	484 KB	Output is correct
5	Correct	2 ms	540 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	556 KB	Output is correct
2	Correct	2 ms	564 KB	Output is correct
3	Correct	2 ms	564 KB	Output is correct
4	Correct	2 ms	564 KB	Output is correct
5	Correct	2 ms	564 KB	Output is correct
6	Correct	19 ms	2364 KB	Output is correct
7	Correct	14 ms	2364 KB	Output is correct
8	Correct	35 ms	4108 KB	Output is correct
9	Correct	12 ms	4108 KB	Output is correct
10	Correct	46 ms	4756 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4756 KB	Output is correct
2	Correct	2 ms	4756 KB	Output is correct
3	Correct	2 ms	4756 KB	Output is correct
4	Correct	2 ms	4756 KB	Output is correct
5	Correct	2 ms	4756 KB	Output is correct
6	Correct	20 ms	4756 KB	Output is correct
7	Correct	14 ms	4756 KB	Output is correct
8	Correct	34 ms	4756 KB	Output is correct
9	Correct	11 ms	4756 KB	Output is correct
10	Correct	61 ms	4860 KB	Output is correct
11	Correct	3 ms	4860 KB	Output is correct
12	Correct	3 ms	4860 KB	Output is correct
13	Correct	26 ms	4860 KB	Output is correct
14	Correct	2 ms	4860 KB	Output is correct
15	Correct	66 ms	4988 KB	Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4988 KB	Output is correct
2	Correct	2 ms	4988 KB	Output is correct
3	Correct	2 ms	4988 KB	Output is correct
4	Correct	2 ms	4988 KB	Output is correct
5	Correct	2 ms	4988 KB	Output is correct
6	Correct	2 ms	4988 KB	Output is correct
7	Correct	2 ms	4988 KB	Output is correct
8	Correct	2 ms	4988 KB	Output is correct
9	Correct	3 ms	4988 KB	Output is correct
10	Correct	3 ms	4988 KB	Output is correct

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4988 KB	Output is correct
2	Correct	2 ms	4988 KB	Output is correct
3	Correct	2 ms	4988 KB	Output is correct
4	Correct	2 ms	4988 KB	Output is correct
5	Correct	2 ms	4988 KB	Output is correct
6	Correct	2 ms	4988 KB	Output is correct
7	Correct	2 ms	4988 KB	Output is correct
8	Correct	2 ms	4988 KB	Output is correct
9	Correct	3 ms	4988 KB	Output is correct
10	Correct	3 ms	4988 KB	Output is correct
11	Correct	17 ms	4988 KB	Output is correct
12	Correct	14 ms	4988 KB	Output is correct
13	Correct	29 ms	4988 KB	Output is correct
14	Correct	16 ms	4988 KB	Output is correct
15	Correct	28 ms	4988 KB	Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4988 KB	Output is correct
2	Correct	2 ms	4988 KB	Output is correct
3	Correct	2 ms	4988 KB	Output is correct
4	Correct	2 ms	4988 KB	Output is correct
5	Correct	2 ms	4988 KB	Output is correct
6	Correct	3 ms	4988 KB	Output is correct
7	Correct	3 ms	4988 KB	Output is correct
8	Correct	2 ms	4988 KB	Output is correct

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4988 KB	Output is correct
2	Correct	2 ms	4988 KB	Output is correct
3	Correct	2 ms	4988 KB	Output is correct
4	Correct	2 ms	4988 KB	Output is correct
5	Correct	3 ms	4988 KB	Output is correct
6	Correct	2 ms	4988 KB	Output is correct
7	Correct	2 ms	4988 KB	Output is correct
8	Correct	3 ms	4988 KB	Output is correct
9	Correct	60 ms	4988 KB	Output is correct
10	Correct	63 ms	4988 KB	Output is correct
11	Correct	17 ms	4988 KB	Output is correct
12	Correct	21 ms	4988 KB	Output is correct
13	Correct	6 ms	4988 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4988 KB	Output is correct
2	Correct	2 ms	4988 KB	Output is correct
3	Correct	3 ms	4988 KB	Output is correct
4	Correct	2 ms	4988 KB	Output is correct
5	Correct	3 ms	4988 KB	Output is correct
6	Correct	2 ms	4988 KB	Output is correct
7	Correct	2 ms	4988 KB	Output is correct
8	Correct	2 ms	4988 KB	Output is correct
9	Correct	63 ms	4988 KB	Output is correct
10	Correct	49 ms	4988 KB	Output is correct
11	Correct	18 ms	4988 KB	Output is correct
12	Correct	21 ms	4988 KB	Output is correct
13	Correct	6 ms	4988 KB	Output is correct
14	Correct	79 ms	4988 KB	Output is correct
15	Correct	96 ms	6512 KB	Output is correct
16	Correct	15 ms	6512 KB	Output is correct
17	Correct	58 ms	6512 KB	Output is correct
18	Correct	30 ms	6512 KB	Output is correct

답안 #66577

Compilation message