답안 #420952

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
420952	2021-06-08T15:19:21 Z	Peti	곤돌라 (IOI14_gondola)	C++14	100 / 100	78 ms	5892 KB

gondola

#include <bits/stdc++.h>
#include "gondola.h"

using namespace std;

int valid(int n, int t[])
{
    rotate(t, min_element(t, t+n), t+n);
    map<int, int> num;
    int last = -n-1;
    bool jo = true;
    for(int i = 0; i < n; i++){
        last++;
        num[t[i]]++;
        if(t[i] <= n){
            if(last < 0)
                last = t[i];
            else if(t[i] != last)
                jo = false;
        }
    }

    for(auto p : num)
        if(p.second > 1)
            return 0;

    return (int)jo;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    for(int i = 0; i < n; i++){
        if(gondolaSeq[i] <= n){
            int x = i-gondolaSeq[i]+1;
            if(x < 0) x += n;
            rotate(gondolaSeq, gondolaSeq + x, gondolaSeq + n);
            break;
        }
    }

    vector<pair<int, int>> v;
    for(int i = 0; i < n; i++)
        if(gondolaSeq[i] > n)
            v.emplace_back(gondolaSeq[i], i+1);
    sort(v.begin(), v.end());

    int ret = 0, x = n;
    for(auto p : v){
        while(x < p.first){
            replacementSeq[ret++] = p.second;
            p.second = ++x;
        }
    }

    return ret;
}

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

const long long mod = (long long)1e9+9;
long long hatvany(long long n, long long h){
    return (h ? hatvany(n*n%mod, h>>1)*(h&1ll ? n : 1ll)%mod : 1ll);
}

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

    bool fix = false;
    vector<int> v;
    for(int i = 0; i < n; i++){
        if(inputSeq[i] <= n)
            fix = true;
        else
            v.push_back(inputSeq[i]);
    }

    if(v.empty())
        return 1;

    sort(v.begin(), v.end());
    long long meg = 1, last = n, db = (long long)v.size();
    for(long long x : v){
        meg = (meg * hatvany(db, x-last-1ll))%mod;
        db--;
        last = x;
    }

    return meg * (!fix ? (long long)n : 1ll) % mod;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	12 ms	2124 KB	Output is correct
7	Correct	30 ms	3592 KB	Output is correct
8	Correct	23 ms	3916 KB	Output is correct
9	Correct	7 ms	1356 KB	Output is correct
10	Correct	78 ms	4416 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	2 ms	204 KB	Output is correct
5	Correct	2 ms	204 KB	Output is correct
6	Correct	31 ms	2196 KB	Output is correct
7	Correct	31 ms	3592 KB	Output is correct
8	Correct	24 ms	3840 KB	Output is correct
9	Correct	7 ms	1356 KB	Output is correct
10	Correct	27 ms	4420 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	0 ms	204 KB	Output is correct
13	Correct	16 ms	1996 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	43 ms	4620 KB	Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	3 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	9 ms	500 KB	Output is correct
12	Correct	12 ms	588 KB	Output is correct
13	Correct	15 ms	1276 KB	Output is correct
14	Correct	9 ms	588 KB	Output is correct
15	Correct	23 ms	2152 KB	Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	41 ms	4392 KB	Output is correct
10	Correct	33 ms	3708 KB	Output is correct
11	Correct	12 ms	1484 KB	Output is correct
12	Correct	21 ms	1732 KB	Output is correct
13	Correct	4 ms	588 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	42 ms	4496 KB	Output is correct
10	Correct	33 ms	3752 KB	Output is correct
11	Correct	12 ms	1500 KB	Output is correct
12	Correct	16 ms	1740 KB	Output is correct
13	Correct	4 ms	588 KB	Output is correct
14	Correct	61 ms	5328 KB	Output is correct
15	Correct	60 ms	5892 KB	Output is correct
16	Correct	10 ms	1356 KB	Output is correct
17	Correct	48 ms	4044 KB	Output is correct
18	Correct	24 ms	2476 KB	Output is correct

답안 #420952

Compilation message