답안 #471437

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
471437	2021-09-09T08:29:58 Z	dung11112003	곤돌라 (IOI14_gondola)	C++11	100 / 100	31 ms	2632 KB

gondola

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

#define taskname ""
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define for0(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex <ld> cd;
typedef vector <cd> vcd;
typedef vector <int> vi;

template<class T> using v2d = vector <vector <T> >;
template<class T> bool uin(T &a, T b)
{
    return a > b ? (a = b, true) : false;
}
template<class T> bool uax(T &a, T b)
{
    return a < b ? (a = b, true) : false;
}

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const ll mod = 1e9 + 9;

int valid(int n, int inputSeq[])
{
    vi vec(inputSeq, inputSeq + n);
    sort(all(vec));
    for0(i, n - 1)
    {
        if (vec[i] == vec[i + 1])
        {
            return 0;
        }
    }
    int d = -1;
    for0(i, n)
    {
        if (inputSeq[i] >= 1 && inputSeq[i] <= n)
        {
            int cur = ((inputSeq[i] - i) % n + n) % n;
            if (d != -1 && d != cur)
            {
                return 0;
            }
            d = cur;
        }
    }
    return 1;
}

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    for0(i, n)
    {
        if (gondolaSeq[i] >= 1 && gondolaSeq[i] <= n)
        {
            int cur = i;
            int need = gondolaSeq[i] - 1;
            if (need < cur)
            {
                rotate(gondolaSeq, gondolaSeq + cur - need, gondolaSeq + n);
            }
            else if (need > cur)
            {
                rotate(gondolaSeq, gondolaSeq + n - (need - cur), gondolaSeq + n);
            }
            break;
        }
    }
    vi pos((int)2e5 + 1, -1);
    for0(i, n)
    {
        pos[gondolaSeq[i]] = i;
    }
    int mx = *max_element(gondolaSeq, gondolaSeq + n);
    vi a(n);
    iota(all(a), 1);
    int id = 0;
    int ansPos = 0;
    auto addAns = [&](int x)
    {
        replacementSeq[ansPos++] = x;
    };
    fore(i, n + 1, mx)
    {
        if (pos[i] != -1)
        {
            addAns(a[pos[i]]);
            a[pos[i]] = i;
        }
        else
        {
            while (id < n && a[id] == gondolaSeq[id])
            {
                id++;
            }
            addAns(a[id]);
            a[id] = i;
        }
    }
    return ansPos;
}

long long power(long long a, long long b)
{
    long long r = 1;
    while (b)
    {
        if (b & 1)
        {
            r = r * a % mod;
        }
        b /= 2;
        a = a * a % mod;
    }
    return r;
}

int countReplacement(int n, int inputSeq[])
{
    vi vec(inputSeq, inputSeq + n);
    sort(all(vec));
    for0(i, n - 1)
    {
        if (vec[i] == vec[i + 1])
        {
            return 0;
        }
    }
    int d = -1;
    for0(i, n)
    {
        if (inputSeq[i] >= 1 && inputSeq[i] <= n)
        {
            int cur = ((inputSeq[i] - i) % n + n) % n;
            if (d != -1 && d != cur)
            {
                return 0;
            }
            d = cur;
        }
    }
    for0(i, n)
    {
        if (inputSeq[i] >= 1 && inputSeq[i] <= n)
        {
            int cur = i;
            int need = inputSeq[i] - 1;
            if (need < cur)
            {
                rotate(inputSeq, inputSeq + cur - need, inputSeq + n);
            }
            else if (need > cur)
            {
                rotate(inputSeq, inputSeq + n - (need - cur), inputSeq + n);
            }
            break;
        }
    }
    vi a;
    for0(i, n)
    {
        if (inputSeq[i] > n)
        {
            a.pb(inputSeq[i]);
        }
    }
    sort(all(a));
    int cnt = 0;
    for0(i, n)
    {
        cnt += (i + 1 != inputSeq[i]);
    }
    int ans = 1, last = n;
    for (auto &x: a)
    {
        ans = (ll)ans * power(cnt, x - last - 1) % mod;
        cnt--;
        last = x;
    }
    if (d == -1)
    {
        ans = (ll)ans * n % mod;
    }
    return ans;
}

Subtask #1
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
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	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	9 ms	492 KB	Output is correct
7	Correct	16 ms	992 KB	Output is correct
8	Correct	13 ms	748 KB	Output is correct
9	Correct	5 ms	480 KB	Output is correct
10	Correct	18 ms	844 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	1 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	8 ms	572 KB	Output is correct
7	Correct	17 ms	972 KB	Output is correct
8	Correct	13 ms	844 KB	Output is correct
9	Correct	5 ms	460 KB	Output is correct
10	Correct	18 ms	852 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	7 ms	588 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	17 ms	936 KB	Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1100 KB	Output is correct
2	Correct	1 ms	972 KB	Output is correct
3	Correct	1 ms	972 KB	Output is correct
4	Correct	1 ms	972 KB	Output is correct
5	Correct	1 ms	972 KB	Output is correct
6	Correct	1 ms	972 KB	Output is correct
7	Correct	1 ms	1100 KB	Output is correct
8	Correct	1 ms	1100 KB	Output is correct
9	Correct	1 ms	1100 KB	Output is correct
10	Correct	1 ms	1100 KB	Output is correct
11	Correct	11 ms	1692 KB	Output is correct
12	Correct	15 ms	1724 KB	Output is correct
13	Correct	13 ms	1612 KB	Output is correct
14	Correct	10 ms	1612 KB	Output is correct
15	Correct	22 ms	2124 KB	Output is correct

Subtask #7
5.0 / 5.0

#	결과	메모리	Grader output
1	Correct	204 KB	Output is correct
2	Correct	204 KB	Output is correct
3	Correct	204 KB	Output is correct

Subtask #8
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	0 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	304 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 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	0 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	21 ms	1760 KB	Output is correct
10	Correct	17 ms	1484 KB	Output is correct
11	Correct	7 ms	844 KB	Output is correct
12	Correct	9 ms	844 KB	Output is correct
13	Correct	2 ms	460 KB	Output is correct

Subtask #10
10.0 / 10.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	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	1 ms	204 KB	Output is correct
9	Correct	22 ms	1760 KB	Output is correct
10	Correct	17 ms	1464 KB	Output is correct
11	Correct	7 ms	844 KB	Output is correct
12	Correct	8 ms	844 KB	Output is correct
13	Correct	2 ms	460 KB	Output is correct
14	Correct	27 ms	2420 KB	Output is correct
15	Correct	31 ms	2632 KB	Output is correct
16	Correct	6 ms	716 KB	Output is correct
17	Correct	21 ms	1780 KB	Output is correct
18	Correct	12 ms	1348 KB	Output is correct

답안 #471437

Compilation message