oj.uz

Submission #379345

# Submission time Handle Problem Language Result Execution time Memory
379345 2021-03-18T02:30:25 Z pavement Gondola (IOI14_gondola) C++17
100 / 100
 32 ms 2544 KB 
#include "gondola.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef double db;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int valid(int n, int inputSeq[]) {
	int pos = -1;
	vector<int> S;
	for (int i = 0; i < n; i++)
		if (inputSeq[i] <= n) {
			pos = i;
			break;
		}
	for (int i = 0; i < n; i++)
		if (inputSeq[i] > n)
			S.pb(inputSeq[i]);
	sort(S.begin(), S.end());
	if (unique(S.begin(), S.end()) != S.end()) return 0;
	if (pos == -1) return 1;
	int curr = inputSeq[pos];
	for (int i = pos; i < n; i++) {
		if (inputSeq[i] <= n && curr != inputSeq[i]) return 0;
		curr++;
		if (curr == n + 1) curr = 1;
	}
	for (int i = 0; i < pos; i++) {
		if (inputSeq[i] <= n && curr != inputSeq[i]) return 0;
		curr++;
		if (curr == n + 1) curr = 1;
	}
	return 1;
}

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
	int pos = -1, l = 0;
	for (int i = 0; i < n; i++)
		if (gondolaSeq[i] <= n) {
			pos = i;
			break;
		}
	int curr = (pos == -1 ? 1 : gondolaSeq[pos]);
	if (pos == -1) pos = 0;
	vector<iii> need;
	for (int i = pos; i < n; i++) {
		if (gondolaSeq[i] > n) need.eb(gondolaSeq[i], curr, i);
		curr++;
		if (curr == n + 1) curr = 1;
	}
	for (int i = 0; i < pos; i++) {
		if (gondolaSeq[i] > n) need.eb(gondolaSeq[i], curr, i);
		curr++;
		if (curr == n + 1) curr = 1;
	}
	sort(need.begin(), need.end());
	int prv = -1;
	for (auto i : need) {
		int iter = 0;
		for (int j = max(prv, n); j < g0(i); j++) {
			replacementSeq[l] = (iter ? l + n : g1(i));
			l++;
			iter++;
		}
		prv = g0(i);
	}
	return l;
}

const int MOD = 1e9 + 9;

int exp_mod(int a, int b) {
	int r = 1;
	while (b) {
		if (b & 1) r = (ll)r * (ll)a % MOD;
		a = (ll)a * (ll)a % MOD;
		b >>= 1;
	}
	return r;
}

int countReplacement(int n, int inputSeq[]) {
	if (!valid(n, inputSeq)) return 0;
    int pos = -1, ans = 1;
	for (int i = 0; i < n; i++)
		if (inputSeq[i] <= n) {
			pos = i;
			break;
		}
	vector<int> need;
	for (int i = 0; i < n; i++)
		if (inputSeq[i] > n) need.pb(inputSeq[i]);
	sort(need.begin(), need.end());
	int prv = -1, lft = need.size();
	for (auto i : need) {
		ans = (ll)ans * (ll)exp_mod(lft, i - max(prv, n) - 1) % MOD;
		prv = i;
		lft--;
	}
	if (pos == -1) ans = (ll)ans * (ll)n % MOD;
	return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory 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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory 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 5 ms 748 KB Output is correct
7 Correct 16 ms 1132 KB Output is correct
8 Correct 10 ms 1004 KB Output is correct
9 Correct 4 ms 492 KB Output is correct
10 Correct 11 ms 1104 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory 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 5 ms 748 KB Output is correct
7 Correct 11 ms 1132 KB Output is correct
8 Correct 13 ms 1004 KB Output is correct
9 Correct 6 ms 492 KB Output is correct
10 Correct 11 ms 1132 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 8 ms 1132 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 13 ms 1388 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory 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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory 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
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory 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 2 ms 512 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 11 ms 1132 KB Output is correct
12 Correct 14 ms 1132 KB Output is correct
13 Correct 16 ms 1540 KB Output is correct
14 Correct 11 ms 1132 KB Output is correct
15 Correct 24 ms 2336 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory 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

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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
9 Correct 21 ms 1540 KB Output is correct
10 Correct 16 ms 1388 KB Output is correct
11 Correct 7 ms 788 KB Output is correct
12 Correct 9 ms 900 KB Output is correct
13 Correct 2 ms 492 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 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 21 ms 1540 KB Output is correct
10 Correct 17 ms 1388 KB Output is correct
11 Correct 7 ms 788 KB Output is correct
12 Correct 9 ms 900 KB Output is correct
13 Correct 2 ms 492 KB Output is correct
14 Correct 29 ms 2332 KB Output is correct
15 Correct 32 ms 2544 KB Output is correct
16 Correct 6 ms 804 KB Output is correct
17 Correct 21 ms 1644 KB Output is correct
18 Correct 12 ms 1260 KB Output is correct