답안 #98753 :: oj.uz

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

gondola

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

using namespace std;

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

int a[Nmax];

int valid(int n, int A[])
{
    map<int,int> ap;

    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;
        }
        else ++ap[i];

    for(auto it : ap)
        if(it.second > 1) return 0;
    return 1;
}

bool cmp(int x, int y)
{
    return a[x] < a[y];
}

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] = A[i];

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

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

    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	2 ms	256 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	3 ms	256 KB	Output is correct
5	Correct	2 ms	256 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	2 ms	256 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	256 KB	Output is correct
6	Correct	7 ms	512 KB	Output is correct
7	Correct	16 ms	640 KB	Output is correct
8	Correct	15 ms	640 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	21 ms	768 KB	Output is correct

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	256 KB	Output is correct
2	Correct	3 ms	256 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	256 KB	Output is correct
6	Correct	8 ms	512 KB	Output is correct
7	Correct	15 ms	640 KB	Output is correct
8	Correct	16 ms	640 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	12 ms	640 KB	Output is correct
11	Incorrect	3 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	2 ms	284 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	3 ms	384 KB	Output is correct
5	Correct	3 ms	384 KB	Output is correct

Subtask #5
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 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
6	Correct	2 ms	384 KB	Output is correct
7	Incorrect	3 ms	380 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	384 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	3 ms	384 KB	Output is correct
6	Correct	2 ms	256 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	3 ms	384 KB	Output is correct
9	Correct	43 ms	3320 KB	Output is correct
10	Correct	29 ms	2568 KB	Output is correct
11	Correct	13 ms	1408 KB	Output is correct
12	Correct	16 ms	1792 KB	Output is correct
13	Incorrect	5 ms	640 KB	Output isn't correct

Subtask #10
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 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	384 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	256 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	37 ms	3328 KB	Output is correct
10	Correct	32 ms	2560 KB	Output is correct
11	Correct	12 ms	1408 KB	Output is correct
12	Correct	15 ms	1664 KB	Output is correct
13	Incorrect	5 ms	640 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

답안 #98753

Compilation message