Submission #1185378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185378		stdfloat	Gondola (IOI14_gondola)	C++20	100 / 100	41 ms	6336 KiB

gondola

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

using ll = long long;

#define ff	first
#define ss	second
#define pii	pair<int, int>

#define sz(x) (int)x.size()

const int md = (int)1e9 + 9;

int pw(int x, int y) {
	int res = 1;
	while (y) {
		if (y & 1) res = (ll)res * x % md;

		y >>= 1;
		x = (ll)x * x % md;
	}

	return res;
}

int valid(int n, int a[]) {
	set<int> s(a, a + n);
	if (sz(s) != n) return 0;

	for (int i = 0; i < n; i++)
		a[i]--;

	int x = -1, y = -1;
	for (int i = 0; i < n; i++) {
		if (a[i] < n) {
			x = i; y = a[i];
		}
	}

	if (!~x) return 1;

	int z = 0;
	while (z++ < n) {
		if (a[x] < n && a[x] != y) return 0;

		y = (y + 1) % n; x = (x + 1) % n;
	}

	return 1;
}

int replacement(int n, int a[], int b[]) {
	for (int i = 0; i < n; i++)
		a[i]--;

	int x = 0, y = 0;
	for (int i = 0; i < n; i++) {
		if (a[i] < n) {
			x = i; y = a[i];
		}
	}

	int z = 0;
	vector<pii> v = {{n - 1, -1}};
	while (z++ < n) {
		if (n <= a[x]) v.push_back({a[x], y});

		y = (y + 1) % n; x = (x + 1) % n;
	}

	sort(v.begin(), v.end());

	x = 0;
	for (int i = 1; i < (int)v.size(); i++) {
		b[x++] = v[i].ss;
		for (int j = v[i - 1].ff + 1; j < v[i].ff; j++)
			b[x++] = j;
	}

	for (int i = 0; i < x; i++)
		b[i]++;

	return x;
}

int countReplacement(int n, int a[]) {
	set<int> s(a, a + n);
	if (sz(s) != n) return 0;

	for (int i = 0; i < n; i++)
		a[i]--;

	int x = -1, y = -1;
	for (int i = 0; i < n; i++) {
		if (a[i] < n) {
			x = i; y = a[i];
		}
	}

	int ans = 1;
	if (!~x) {
		x = 0;
		ans = n;
	}

	int z = 0;
	vector<pii> v = {{n - 1, -1}};
	while (z++ < n) {
		if (n <= a[x]) v.push_back({a[x], y});

		y = (y + 1) % n; x = (x + 1) % n;
	}

	sort(v.begin(), v.end());

	for (int i = 1; i < sz(v); i++)
		ans = (ll)ans * pw(sz(v) - i, v[i].ff - v[i - 1].ff - 1) % md;

	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