답안 #978915

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
978915	2024-05-10T02:24:31 Z	Amaarsaa	곤돌라 (IOI14_gondola)	C++14	100 / 100	61 ms	5928 KB

gondola

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include "gondola.h"
using namespace std;
using ll = long long;
 
ll MOD = 1e9 + 9;
 
int valid(int n, int g[]) {
	set <int> s;
	for (int i = 0; i < n; i++) {
		if (s.count(g[i])) return 0;
		s.insert(g[i]);
	}
	int p = 0;
	for (int i = 0; i < n; i++) if (g[i] <= n) p = (g[i] - i + n) % n;
	for (int i = 0; i < n; i++) if (g[i] <= n && (g[i] - i + n) % n != p) return 0;
	return 1;
}
 
int replacement(int n, int g[], int r[]) {
	int p = 0, cnt = 0, mx = 0;
	vector <int> rev(1e6 + 1, -1);
	vector <int> cur(n, 0);
	for (int i = 0; i < n; i++) {
		if (g[i] <= n) { p = (g[i] - i + n) % n; cnt++; }
		mx = max(mx, g[i]);
		rev[g[i]] = i;
	}
	for (int i = 0; i < n; i++) cur[i] = (i + p) % n;
	cur[(n - p) % n] = n;
	for (int i = n + 1; i <= mx; i++) {
		if (rev[i] == -1) { r[i - n - 1] = cur[rev[mx]]; cur[rev[mx]] = i; }
		else { r[i - n - 1] = cur[rev[i]]; cur[rev[i]] = i; }
	}
	return mx - n;
}
 
ll pow(ll a, int b) {
	ll ret = 1;
	for (int i = 30; i >= 0; i--) {
		ret *= ret; ret %= MOD;
		if (b & (1 << i)) { ret *= a; ret %= MOD; }
	}
	return ret;
}
 
int countReplacement(int n, int g[]) {
	if (!valid(n, g)) return 0;
	ll cnt = 0, ans = 1;
	sort(g, g + n);
	for (int i = 0; i < n; i++) if (g[i] <= n) cnt++;
	if (cnt == 0) ans = n;
	if (cnt == n) return 1;
	ans *= pow(n - cnt, g[cnt] - n - 1);
	ans %= MOD;
	for (int i = cnt + 1; i < n; i++) {
		ans *= pow(n - i, g[i] - g[i - 1] - 1);
		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	344 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	0 ms	600 KB	Output is correct
6	Correct	10 ms	2176 KB	Output is correct
7	Correct	6 ms	604 KB	Output is correct
8	Correct	19 ms	3848 KB	Output is correct
9	Correct	6 ms	1528 KB	Output is correct
10	Correct	25 ms	4560 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	344 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	10 ms	2136 KB	Output is correct
7	Correct	6 ms	600 KB	Output is correct
8	Correct	19 ms	3932 KB	Output is correct
9	Correct	6 ms	1372 KB	Output is correct
10	Correct	24 ms	4588 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	12 ms	2140 KB	Output is correct
14	Correct	1 ms	344 KB	Output is correct
15	Correct	30 ms	4600 KB	Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4188 KB	Output is correct
2	Correct	1 ms	4188 KB	Output is correct
3	Correct	1 ms	4188 KB	Output is correct
4	Correct	1 ms	4188 KB	Output is correct
5	Correct	1 ms	4324 KB	Output is correct
6	Correct	1 ms	4372 KB	Output is correct
7	Correct	1 ms	4188 KB	Output is correct
8	Correct	2 ms	4188 KB	Output is correct
9	Correct	1 ms	4188 KB	Output is correct
10	Correct	2 ms	4188 KB	Output is correct
11	Correct	7 ms	5260 KB	Output is correct
12	Correct	8 ms	5468 KB	Output is correct
13	Correct	9 ms	5072 KB	Output is correct
14	Correct	7 ms	5208 KB	Output is correct
15	Correct	19 ms	5212 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	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 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	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct

Subtask #9
15.0 / 15.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	600 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	600 KB	Output is correct
6	Correct	0 ms	444 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	39 ms	4628 KB	Output is correct
10	Correct	31 ms	3932 KB	Output is correct
11	Correct	12 ms	1732 KB	Output is correct
12	Correct	16 ms	1884 KB	Output is correct
13	Correct	3 ms	604 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 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	1 ms	444 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	38 ms	4444 KB	Output is correct
10	Correct	31 ms	3664 KB	Output is correct
11	Correct	12 ms	1740 KB	Output is correct
12	Correct	14 ms	1884 KB	Output is correct
13	Correct	3 ms	604 KB	Output is correct
14	Correct	49 ms	5460 KB	Output is correct
15	Correct	61 ms	5928 KB	Output is correct
16	Correct	9 ms	1372 KB	Output is correct
17	Correct	36 ms	4188 KB	Output is correct
18	Correct	19 ms	2396 KB	Output is correct

답안 #978915

Compilation message