oj.uz

Submission #1015196

# Submission time Handle Problem Language Result Execution time Memory
1015196 2024-07-06T07:20:15 Z AmirAli_H1 Gondola (IOI14_gondola) C++17
100 / 100
 45 ms 8016 KB 
// In the name of Allah

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

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 3e5 + 4;
const int mod = 1e9 + 9;
map<int, int> ind; int val[maxn];

ll power(ll a, ll b) {
	if (b == 0) return 1;
	return power(a * a % mod, b / 2) * ((b & 1) ? a : 1) % mod;
}

int valid(int n, int a[]) {
	int j = -1, mx = 0;
	for (int i = 0; i < n; i++) {
		a[i]--;
		if (ind.find(a[i]) != ind.end()) return 0;
		else ind[a[i]] = i;
		if (a[i] > a[mx]) mx = i;
		if (a[i] < n) {
			int k = (i - a[i] + n) % n;
			if (j == -1 || j == k) j = k;
			else return 0;
		}
	}
	return 1;
}

int replacement(int n, int a[], int res[]) {
	int j = -1, mx = 0;
	for (int i = 0; i < n; i++) {
		a[i]--;
		if (ind.find(a[i]) != ind.end()) return 0;
		else ind[a[i]] = i;
		if (a[i] > a[mx]) mx = i;
		if (a[i] < n) {
			int k = (i - a[i] + n) % n;
			if (j == -1 || j == k) j = k;
			else return 0;
		}
	}
	if (j == -1) j = 0;
	
	for (int i = j; i < j + n; i++) val[i % n] = i - j;
	for (int i = n; i <= a[mx]; i++) {
		if (ind.find(i) != ind.end()) {
			int j = ind[i];
			res[i - n] = val[j] + 1;
			val[j] = i;
		}
		else {
			int j = ind[a[mx]];
			res[i - n] = val[j] + 1;
			val[j] = i;
		}
	}
	return (a[mx] + 1) - n;
}

int countReplacement(int n, int a[]) {
	int j = -1, mx = 0;
	for (int i = 0; i < n; i++) {
		a[i]--;
		if (ind.find(a[i]) != ind.end()) return 0;
		else ind[a[i]] = i;
		if (a[i] > a[mx]) mx = i;
		if (a[i] < n) {
			int k = (i - a[i] + n) % n;
			if (j == -1 || j == k) j = k;
			else return 0;
		}
	}
	
	ll ans = 1, R = 0;
	for (int i = 0; i < n; i++) {
		if (ind.find(i) == ind.end()) R++;
	}
	sort(a, a + n); int lst = n;
	for (int i = 0; i < n; i++) {
		if (a[i] < lst) continue;
		ans *= power(R, a[i] - lst); ans %= mod;
		lst = a[i] + 1; R--;
	}
	if (j == -1) {
		ans *= n; ans %= mod;
	}
	return ans;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 9 ms 4396 KB Output is correct
7 Correct 6 ms 3240 KB Output is correct
8 Correct 18 ms 6464 KB Output is correct
9 Correct 5 ms 3676 KB Output is correct
10 Correct 21 ms 7016 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 9 ms 4324 KB Output is correct
7 Correct 8 ms 3156 KB Output is correct
8 Correct 17 ms 6232 KB Output is correct
9 Correct 5 ms 3676 KB Output is correct
10 Correct 21 ms 7028 KB Output is correct
11 Correct 1 ms 2648 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 3 ms 2652 KB Output is correct
14 Correct 0 ms 2408 KB Output is correct
15 Correct 6 ms 3164 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2496 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 21 ms 6980 KB Output is correct
12 Correct 22 ms 7516 KB Output is correct
13 Correct 20 ms 4808 KB Output is correct
14 Correct 23 ms 6996 KB Output is correct
15 Correct 19 ms 4380 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 38 ms 6484 KB Output is correct
10 Correct 40 ms 5664 KB Output is correct
11 Correct 10 ms 3672 KB Output is correct
12 Correct 14 ms 3932 KB Output is correct
13 Correct 4 ms 2648 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 36 ms 6512 KB Output is correct
10 Correct 27 ms 5716 KB Output is correct
11 Correct 10 ms 3672 KB Output is correct
12 Correct 11 ms 3928 KB Output is correct
13 Correct 5 ms 2652 KB Output is correct
14 Correct 39 ms 7292 KB Output is correct
15 Correct 45 ms 8016 KB Output is correct
16 Correct 11 ms 3344 KB Output is correct
17 Correct 31 ms 6180 KB Output is correct
18 Correct 19 ms 4580 KB Output is correct