Submission #614782

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
614782	2022-07-31T04:52:22 Z	cheissmart	Gondola (IOI14_gondola)	C++14	100 / 100	58 ms	6076 KB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, M = 1e9 + 9;

int valid(int n, int a[]) {
    int he = -1;
    set<int> s;
    for(int i = 0; i < n; i++) {
        if(s.count(a[i]))
            return 0;
        s.insert(a[i]);
    }
    for(int i = 0; i < n; i++) if(a[i] <= n) {
        int be = (i - a[i] + n) % n;
        if(he != -1 && he != be)
            return 0;
        he = be;
    }
    return 1;
}

int replacement(int n, int a[], int b[]) {
    assert(valid(n, a));
    int sz = 0, mx = 0;
    map<int, int> mp;
    int pos = -1;
    for(int i = 0; i < n; i++) {
        mx = max(mx, a[i]);
        if(a[i] >= n) {
            mp[a[i]] = i;
        } else {
            pos = i;
        }
    }
    if(pos == -1) {
        for(int i = 0; i < n; i++)
            a[i] = i + 1;
    } else {
        for(int i = pos + 1; i < n; i++) {
            a[i] = (a[pos] + i - pos + n - 1) % n + 1;
        }
        for(int i = 0; i < pos; i++) {
            a[i] = (a[pos] + i - pos + n - 1) % n + 1;
        }
    }
    for(int i = n + 1; i <= mx; i++) {
        if(mp.count(i)) {
            b[sz++] = a[mp[i]];
            a[mp[i]] = i;
        } else {
            b[sz++] = a[mp[mx]];
            a[mp[mx]] = i;
        }
    }
    return sz;
}

int qpow(int a, int b) {
    if(b == 0) return 1;
    ll t = qpow(a, b / 2);
    t = t * t % M;
    if(b & 1) t = t * a % M;
    return t;
}

int countReplacement(int n, int a[]) {
    if(!valid(n, a)) return 0;
    int mx = 0;
    vi aux;
    for(int i = 0; i < n; i++) {
        mx = max(mx, a[i]);
        if(a[i] > n) {
            aux.PB(a[i]);
        }
    }
    aux.PB(n);
    int ans = 1;
    sort(ALL(aux), greater<int>());
    for(int i = 0; i + 1 < SZ(aux); i++) {
        ans = 1LL * ans * qpow(i + 1, aux[i] - aux[i + 1] - 1) % M;
    }
    if(SZ(aux) == n + 1) ans = 1LL * ans * n % M;
    return ans;
}

Subtask #1
5.0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Correct	212 KB	Output is correct
4	Correct	212 KB	Output is correct
5	Correct	212 KB	Output is correct

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	12 ms	2208 KB	Output is correct
7	Correct	9 ms	596 KB	Output is correct
8	Correct	24 ms	3840 KB	Output is correct
9	Correct	10 ms	1364 KB	Output is correct
10	Correct	41 ms	4524 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	14 ms	2188 KB	Output is correct
7	Correct	9 ms	596 KB	Output is correct
8	Correct	22 ms	3884 KB	Output is correct
9	Correct	7 ms	1372 KB	Output is correct
10	Correct	35 ms	4508 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	15 ms	2004 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	36 ms	4884 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	300 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Correct	212 KB	Output is correct
4	Correct	212 KB	Output is correct
5	Correct	212 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	2 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	34 ms	4268 KB	Output is correct
12	Correct	30 ms	4888 KB	Output is correct
13	Correct	35 ms	2752 KB	Output is correct
14	Correct	28 ms	4160 KB	Output is correct
15	Correct	37 ms	2868 KB	Output is correct

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct

Subtask #8
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct

Subtask #9
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	37 ms	3916 KB	Output is correct
10	Correct	28 ms	3296 KB	Output is correct
11	Correct	10 ms	1332 KB	Output is correct
12	Correct	13 ms	1696 KB	Output is correct
13	Correct	3 ms	596 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	304 KB	Output is correct
5	Correct	1 ms	244 KB	Output is correct
6	Correct	1 ms	304 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	41 ms	4276 KB	Output is correct
10	Correct	30 ms	3624 KB	Output is correct
11	Correct	12 ms	1580 KB	Output is correct
12	Correct	17 ms	1776 KB	Output is correct
13	Correct	3 ms	596 KB	Output is correct
14	Correct	44 ms	5068 KB	Output is correct
15	Correct	58 ms	6076 KB	Output is correct
16	Correct	9 ms	1368 KB	Output is correct
17	Correct	33 ms	4080 KB	Output is correct
18	Correct	19 ms	2388 KB	Output is correct

Submission #614782

Compilation message