Submission #1321554

#	Time	Username	Problem	Language	Result	Execution time	Memory
1321554		orgiloogii	Gondola (IOI14_gondola)	C++20	60 / 100	32 ms	5152 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int valid(int n, int g[]) {
	int idx = -1;
	map <int, bool> vis;
	for (int i = 0;i < n;i++) {
		if (vis[g[i]] == true) return 0;
		vis[g[i]] = true;
		if (g[i] <= n && idx == -1) {
			idx = i;
		}
	}
	if (idx == -1) return 1;
	int cnt = g[idx];
	for (int i = idx + 1;;i++) {
		i %= n;
		if (i == idx) break;
		cnt %= n;
		cnt++;
		if (g[i] <= n && g[i] != cnt) return 0;
	}
	return 1;
}

//----------------------

int replacement(int n, int g[], int r[]) {
    int idx = -1;
	map <int, bool> vis;
	int mx = 0;
	for (int i = 0;i < n;i++) {
		if (vis[g[i]] == true) return 0;
		vis[g[i]] = true;
		if (g[i] <= n && idx == -1) {
			idx = i;
		}
		mx = max(mx, g[i]);
	}
	int sz = 0;
	int exp[n] = {0};
	if (idx == -1) {
		exp[0] = 1;
		int cnt = 1;
		for (int i = 1;;i++) {
			i %= n;
			if (i == 0) break;
			cnt %= n;
			cnt++;
			exp[i] = cnt;
		}
	}
	else {
		exp[idx] = g[idx];
		int cnt = g[idx];
		for (int i = idx + 1;;i++) {
			i %= n;
			if (i == idx) break;
			cnt %= n;
			cnt++;
			exp[i] = cnt;
		}
	}
	// for (int i = 0;i < n;i++) {
	// 	cout << exp[i] << ' ';
	// }
	// cout << endl;
	vector <pair <int, int>> upd;
	for (int i = 0;i < n;i++) {
		if (exp[i] != g[i]) {
			upd.push_back({g[i], exp[i]});
		}
	}
	sort(upd.begin(), upd.end());
	for (auto [x, y] : upd) {
		r[sz] = y;
		sz++;
		for (int i = n + sz;i < x;i++) {
			r[sz] = i;
			sz++;
		}
	}
	return mx - n;
}
const int mod = 1e9 + 9;

int pow(int x, int y) {
    int res;
    if (y == 0)
        return 1;
    res = pow(x, y / 2) % mod;
    if (y % 2 == 0)
        return res * res % mod;
    else
        return ((x * res) % mod * res) % mod;
}

int countReplacement(int n, int g[]) {
	if (!valid(n, g)) {
		return 0;
	}
	ll mult = n;
	vector <ll> saves;
	for (int i = 0;i < n;i++) {
		if (g[i] > n) {
			saves.push_back(g[i]);
		}
		if (g[i] <= n) {
			mult = 1;
		}
	}

	sort(saves.begin(), saves.end());
	ll curr = n;
	int sz = saves.size();
	ll res = 1;
	for (int i = 0;i < saves.size();i++) {
		int iter = saves[i] - curr - 1;
		if (iter == 0) {
			sz--;
			continue;
		}
		res *= pow(sz, iter);
		res %= mod;
		sz--;
		curr = saves[i];
	}
	return (res * mult) % mod;
}

• 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: 0 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10