답안 #1033167

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1033167	2024-07-24T13:32:45 Z	c2zi6	곤돌라 (IOI14_gondola)	C++14	100 / 100	39 ms	7184 KB

gondola

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "gondola.h"

int valid(int n, int inputSeq[]) {
    VI a;
    rep(i, n) {
        if (inputSeq[i] <= n) {
            int start = i - inputSeq[i] + 1;
            if (start < n) start += n;
            replr(i, start, start+n-1) a.pb(inputSeq[i%n]);
            break;
        }
    }
    if (a.size() == 0) {
        rep(i, n) a.pb(inputSeq[i]);
    }
    set<int> st;
    for (int x : a) st.insert(x);
    if (st.size() != a.size()) return false;
    rep(i, n) {
        if (a[i] <= n) {
            if (a[i] != i+1) return false;
        }
    }
    return true;
}

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

int replacement(int n, int inputSeq[], int replacementSeq[]) {
    VI a;
    rep(i, n) {
        if (inputSeq[i] <= n) {
            int start = i - inputSeq[i] + 1;
            if (start < n) start += n;
            replr(i, start, start+n-1) a.pb(inputSeq[i%n]);
            break;
        }
    }
    if (a.size() == 0) {
        rep(i, n) a.pb(inputSeq[i]);
    }
    for (int& x : a) x--;
    int mx = 0;
    VI idx(250'000, -1);
    rep(i, n) {
        setmax(mx, a[i]);
        idx[a[i]] = i;
    }
    VI ans;

    map<int, int> cur;
    rep(i, n) if (idx[i] == -1) {
        cur[i] = i;
    }

    replr(i, n, mx) {
        if (idx[i] == -1) {
            auto it = cur.begin();
            ans.pb(it->ss);
            it->ss = i;
        } else {
            auto it = cur.lower_bound(idx[i]);
            ans.pb(it->ss);
            it->ss = i;
            cur.erase(it);
        }
    }
    rep(i, ans.size()) replacementSeq[i] = ans[i]+1;
    return ans.size();
}

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

const ll MOD = 1e9 + 9;
ll binpow(ll a, ll b) {
    if (b == 0) return 1l;
    if (b & 1) return binpow(a, b-1) * a % MOD;
    ll ret = binpow(a, b/2);
    return ret * ret % MOD;
}
int countReplacement(int n, int inputSeq[]) {
    VI a;
    rep(i, n) {
        if (inputSeq[i] <= n) {
            int start = i - inputSeq[i] + 1;
            if (start < n) start += n;
            replr(i, start, start+n-1) a.pb(inputSeq[i%n]);
            break;
        }
    }
    bool ardyoq = false;
    if (a.size() == 0) {
        ardyoq = true;
        rep(i, n) a.pb(inputSeq[i]);
    }
    set<int> st;
    for (int x : a) st.insert(x);
    if (st.size() != a.size()) return 0;
    rep(i, n) if (a[i] <= n && a[i] != i+1) return 0;
    for (int& x : a) x--;
    int mx = 0;
    rep(i, n) setmax(mx, a[i]);
    VI ka;
    ka.pb(n-1);
    ll cur = 0;
    rep(i, n) {
        if (a[i] >= n) {
            cur++;
            ka.pb(a[i]);
        }
    }
    sort(all(ka));
    ll ans = 1;
    rep(i, ka.size()-1) {
        ll b = ka[i+1] - ka[i] - 1;
        ans *= binpow(cur--, b);
        ans %= MOD;
    }
    if (ardyoq) {
        ans *= n;
        ans %= MOD;
    }
    return ans;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	444 KB	Output is correct
6	Correct	8 ms	2516 KB	Output is correct
7	Correct	20 ms	4564 KB	Output is correct
8	Correct	19 ms	4636 KB	Output is correct
9	Correct	5 ms	1628 KB	Output is correct
10	Correct	18 ms	5412 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	444 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	9 ms	2620 KB	Output is correct
7	Correct	20 ms	4564 KB	Output is correct
8	Correct	16 ms	4564 KB	Output is correct
9	Correct	5 ms	1628 KB	Output is correct
10	Correct	19 ms	5332 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	10 ms	2488 KB	Output is correct
14	Correct	1 ms	344 KB	Output is correct
15	Correct	24 ms	5584 KB	Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1372 KB	Output is correct
2	Correct	1 ms	1372 KB	Output is correct
3	Correct	1 ms	1372 KB	Output is correct
4	Correct	1 ms	1372 KB	Output is correct
5	Correct	1 ms	1372 KB	Output is correct
6	Correct	1 ms	1372 KB	Output is correct
7	Correct	1 ms	1372 KB	Output is correct
8	Correct	1 ms	1372 KB	Output is correct
9	Correct	1 ms	1372 KB	Output is correct
10	Correct	1 ms	1372 KB	Output is correct
11	Correct	8 ms	2408 KB	Output is correct
12	Correct	9 ms	2884 KB	Output is correct
13	Correct	17 ms	3900 KB	Output is correct
14	Correct	6 ms	2512 KB	Output is correct
15	Correct	16 ms	3792 KB	Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	25 ms	5324 KB	Output is correct
10	Correct	22 ms	4448 KB	Output is correct
11	Correct	8 ms	1884 KB	Output is correct
12	Correct	9 ms	2140 KB	Output is correct
13	Correct	2 ms	872 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	396 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	26 ms	5292 KB	Output is correct
10	Correct	21 ms	4528 KB	Output is correct
11	Correct	13 ms	1880 KB	Output is correct
12	Correct	16 ms	2140 KB	Output is correct
13	Correct	4 ms	856 KB	Output is correct
14	Correct	39 ms	6612 KB	Output is correct
15	Correct	38 ms	7184 KB	Output is correct
16	Correct	11 ms	1628 KB	Output is correct
17	Correct	26 ms	4864 KB	Output is correct
18	Correct	14 ms	3028 KB	Output is correct

답안 #1033167

Compilation message