Submission #379345

#	Time	Username	Problem	Language	Result	Execution time	Memory
379345		pavement	Gondola (IOI14_gondola)	C++17	100 / 100	32 ms	2544 KiB

gondola

#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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 20 / 20
• Subtask 7: 5 / 5
• Subtask 8: 15 / 15
• Subtask 9: 15 / 15
• Subtask 10: 10 / 10