답안 #356816

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
356816	2021-01-23T18:20:01 Z	NachoLibre	곤돌라 (IOI14_gondola)	C++17	100 / 100	31 ms	3304 KB

gondola

#include <bits/stdc++.h>
using namespace std;
#ifndef wambule
#include "gondola.h"
#endif

const int mod = 1000000009;
int P(int a, int b) {
	if(b == 0) return 1;
	if(b & 1) return 1ll * P(a, b - 1) * a % mod;
	int c = P(a, b / 2);
	return 1ll * c * c % mod;
}

void G(int a[], int b[], int n) {
	for(int i = 0; i < n; ++i) a[i] = b[i];
}

void D(int a[], int n) {
	int j = 0;
	for(int i = 0; i < n; ++i) {
		if(a[i] <= n) {
			j = i - a[i] + 1;
			if(j < 0) j += n;
			break;
		}
	}
	int b[n];
	G(b, a, n);
	for(int i = j; i < n; ++i) {
		a[i - j] = b[i];
	}
	for(int i = 0; i < j; ++i) {
		a[n - j + i] = b[i];
	}
}

int valid(int n, int _g[]) {
	int g[n];
	G(g, _g, n);
	D(g, n);
	int d[n];
	G(d, g, n);
	sort(d, d + n);
	for(int i = 1; i < n; ++i) {
		if(d[i] == d[i - 1]) return 0;
	}
	for(int i = 0; i < n; ++i) {
		if(g[i] <= n && g[i] != i + 1) return 0;
	}
	return 1;
}

int replacement(int n, int _g[], int r[]) {
	int g[n];
	G(g, _g, n);
	D(g, n);
	vector<pair<int, int> > v;
	for(int i = 0; i < n; ++i) {
		if(g[i] > n) {
			v.push_back({g[i], i});
		}
	}
	sort(v.begin(), v.end());
	int x = n + 1, rg = 0;
	for(int i = 0; i < (int)v.size(); ++i) {
		int gf = v[i].second + 1;
		while(x <= v[i].first) {
			r[rg] = gf;
			gf = x;
			++x;
			++rg;
		}
	}
	return rg;
}

int countReplacement(int n, int _g[]) {
	int g[n];
	G(g, _g, n);
	if(!valid(n, g)) return 0;
	vector<int> v = {n};
	sort(g, g + n);
	for(int i = 0; i < n; ++i) {
		if(g[i] > n) {
			v.push_back(g[i]);
		}
	}
	int dr = (g[0] > n ? n : 1);
	for(int i = 1; i < (int)v.size(); ++i) {
		dr = 1ll * dr * P((int)v.size() - i, v[i] - v[i - 1] - 1) % mod;
	}
	return dr;
}

#ifdef wambule
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	return 0;
}
#endif

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	0 ms	364 KB	Output is correct
4	Correct	0 ms	364 KB	Output is correct
5	Correct	1 ms	504 KB	Output is correct
6	Correct	5 ms	748 KB	Output is correct
7	Correct	16 ms	1408 KB	Output is correct
8	Correct	10 ms	1132 KB	Output is correct
9	Correct	3 ms	620 KB	Output is correct
10	Correct	11 ms	1260 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	512 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	0 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	5 ms	748 KB	Output is correct
7	Correct	16 ms	1516 KB	Output is correct
8	Correct	10 ms	1132 KB	Output is correct
9	Correct	4 ms	620 KB	Output is correct
10	Correct	11 ms	1260 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	7 ms	748 KB	Output is correct
14	Correct	0 ms	364 KB	Output is correct
15	Correct	17 ms	1408 KB	Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	0 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	16 ms	1260 KB	Output is correct
12	Correct	18 ms	1388 KB	Output is correct
13	Correct	16 ms	1532 KB	Output is correct
14	Correct	9 ms	1260 KB	Output is correct
15	Correct	26 ms	2424 KB	Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	492 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	0 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	24 ms	1804 KB	Output is correct
10	Correct	17 ms	1644 KB	Output is correct
11	Correct	7 ms	876 KB	Output is correct
12	Correct	8 ms	1004 KB	Output is correct
13	Correct	3 ms	512 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	0 ms	364 KB	Output is correct
8	Correct	0 ms	364 KB	Output is correct
9	Correct	22 ms	1900 KB	Output is correct
10	Correct	18 ms	1644 KB	Output is correct
11	Correct	7 ms	876 KB	Output is correct
12	Correct	9 ms	1024 KB	Output is correct
13	Correct	2 ms	492 KB	Output is correct
14	Correct	28 ms	3176 KB	Output is correct
15	Correct	31 ms	3304 KB	Output is correct
16	Correct	6 ms	1004 KB	Output is correct
17	Correct	22 ms	2304 KB	Output is correct
18	Correct	12 ms	1644 KB	Output is correct

답안 #356816

Compilation message