답안 #98752 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
98752	2019-02-25T15:31:32 Z	Alexa2001	곤돌라 (IOI14_gondola)	C++17	35 / 100	24 ms	1536 KB

gondola

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

using namespace std;

const int Nmax = 250005, Mod = 1e9 + 9;
typedef long long ll;

int ap[Nmax], a[Nmax];

int valid(int n, int A[])
{
    int i, rot = Mod;
    for(i=0; i<n; ++i)
        if(A[i] <= n)
        {
            if(rot == Mod) rot = (n + i - A[i]) % n;
                else if(rot != (n + i - A[i]) % n) return 0;
        }
    return 1;
}

int replacement(int n, int A[], int ans[])
{
    int i, last = n+1, rot = 0;
    vector<int> v;

    for(i=0; i<n; ++i)
        if(A[i] <= n) rot = (A[i] - 1) - i;
    if(rot < 0) rot += n;

    for(i=0; i<n; ++i) a[(i + rot + n) % n] = A[i];

    for(i=0; i<n; ++i)
        if(a[i] > n) v.push_back(i);

    sort(v.begin(), v.end());

    int nr = 0;
    for(auto it : v)
    {
        ans[nr++] = it+1;
        for(i=last; i<a[it]; ++i) ans[nr++] = i;
        last = a[it];
    }
    return nr;
}

ll power(ll a, int b)
{
    ll ans = 1;
    while(b)
    {
        if(b&1) ans = ans * a % Mod;
        a = a * a % Mod; b >>= 1;
    }
    return ans;
}

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

    int i;
    vector<int> v;
    for(i=0; i<n; ++i)
        if(A[i] > n) v.push_back(A[i] - n);

    sort(v.begin(), v.end());
    int m = v.size();
    ll ans = 1;

    int last = 0;
    for(auto it : v)
    {
        ans *= power(m, it - last - 1);
        ans %= Mod;
        --m;
        last = it;
    }
    return (int) ans;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	3 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	11 ms	768 KB	Output is correct
7	Correct	15 ms	1152 KB	Output is correct
8	Correct	13 ms	1024 KB	Output is correct
9	Correct	5 ms	512 KB	Output is correct
10	Correct	12 ms	1152 KB	Output is correct

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	408 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	3 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	3 ms	384 KB	Output is correct
6	Correct	7 ms	768 KB	Output is correct
7	Correct	15 ms	1280 KB	Output is correct
8	Correct	15 ms	1024 KB	Output is correct
9	Correct	5 ms	512 KB	Output is correct
10	Correct	24 ms	1152 KB	Output is correct
11	Incorrect	2 ms	384 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #4
5.0 / 5.0

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

Subtask #5
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	3 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Incorrect	5 ms	512 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	3 ms	384 KB	Output is correct
4	Correct	3 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Incorrect	6 ms	512 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	384 KB	Output is correct
2	Correct	1 ms	512 KB	Output is correct
3	Correct	2 ms	304 KB	Output is correct
4	Correct	2 ms	256 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	3 ms	384 KB	Output is correct
7	Correct	2 ms	304 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	20 ms	1532 KB	Output is correct
10	Correct	22 ms	1296 KB	Output is correct
11	Correct	10 ms	896 KB	Output is correct
12	Correct	10 ms	896 KB	Output is correct
13	Incorrect	5 ms	392 KB	Output isn't correct

Subtask #10
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	512 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	3 ms	256 KB	Output is correct
4	Correct	3 ms	372 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	3 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	21 ms	1536 KB	Output is correct
10	Correct	15 ms	1408 KB	Output is correct
11	Correct	8 ms	828 KB	Output is correct
12	Correct	12 ms	896 KB	Output is correct
13	Incorrect	4 ms	384 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

답안 #98752

Compilation message