oj.uz

Submission #783218

# Submission time Handle Problem Language Result Execution time Memory
783218 2023-07-14T18:05:56 Z zsombor Gondola (IOI14_gondola) C++17
100 / 100
 59 ms 5896 KB 
#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

# 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

Subtask #2
5.0 / 5.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 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 13 ms 2208 KB Output is correct
7 Correct 6 ms 596 KB Output is correct
8 Correct 23 ms 3924 KB Output is correct
9 Correct 7 ms 1364 KB Output is correct
10 Correct 24 ms 4508 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 10 ms 2204 KB Output is correct
7 Correct 6 ms 596 KB Output is correct
8 Correct 19 ms 3864 KB Output is correct
9 Correct 6 ms 1364 KB Output is correct
10 Correct 24 ms 4532 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 12 ms 1976 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 30 ms 4564 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 3 ms 4180 KB Output is correct
4 Correct 2 ms 4148 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 2 ms 4180 KB Output is correct
7 Correct 2 ms 4180 KB Output is correct
8 Correct 2 ms 4180 KB Output is correct
9 Correct 3 ms 4180 KB Output is correct
10 Correct 2 ms 4180 KB Output is correct
11 Correct 8 ms 4820 KB Output is correct
12 Correct 13 ms 4840 KB Output is correct
13 Correct 10 ms 4692 KB Output is correct
14 Correct 7 ms 4820 KB Output is correct
15 Correct 15 ms 4948 KB Output is correct

Subtask #7
5.0 / 5.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

Subtask #8
15.0 / 15.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 1 ms 212 KB Output is correct
7 Correct 1 ms 260 KB Output is correct
8 Correct 1 ms 224 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 1 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 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 39 ms 4012 KB Output is correct
10 Correct 32 ms 3408 KB Output is correct
11 Correct 12 ms 1364 KB Output is correct
12 Correct 15 ms 1620 KB Output is correct
13 Correct 4 ms 628 KB Output is correct

Subtask #10
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 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 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 39 ms 3980 KB Output is correct
10 Correct 31 ms 3268 KB Output is correct
11 Correct 16 ms 1416 KB Output is correct
12 Correct 14 ms 1624 KB Output is correct
13 Correct 4 ms 596 KB Output is correct
14 Correct 53 ms 4492 KB Output is correct
15 Correct 59 ms 5896 KB Output is correct
16 Correct 10 ms 1344 KB Output is correct
17 Correct 37 ms 4092 KB Output is correct
18 Correct 20 ms 2472 KB Output is correct