Submission #1321574

#	Time	Username	Problem	Language	Result	Execution time	Memory
1321574		orgiloogii	Gondola (IOI14_gondola)	C++20	60 / 100	35 ms	7040 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int valid(int n, int g[]) {
	ll idx = -1;
	map <ll, bool> vis;
	for (ll 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;
	ll cnt = g[idx];
	for (ll 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[]) {
    ll idx = -1;
	map <ll, bool> vis;
	ll mx = 0;
	for (ll 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, 1ll * g[i]);
	}
	ll sz = 0;
	ll exp[n] = {0};
	if (idx == -1) {
		exp[0] = 1;
		ll cnt = 1;
		for (ll i = 1;;i++) {
			i %= n;
			if (i == 0) break;
			cnt %= n;
			cnt++;
			exp[i] = cnt;
		}
	}
	else {
		exp[idx] = g[idx];
		ll cnt = g[idx];
		for (ll i = idx + 1;;i++) {
			i %= n;
			if (i == idx) break;
			cnt %= n;
			cnt++;
			exp[i] = cnt;
		}
	}
	// for (ll i = 0;i < n;i++) {
	// 	cout << exp[i] << ' ';
	// }
	// cout << endl;
	vector <pair <ll, ll>> upd;
	for (ll 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 (ll i = n + sz;i < x;i++) {
			r[sz] = i;
			sz++;
		}
	}
	return mx - n;
}
const ll mod = 1e9 + 9;

ll poww(ll x, ll y) {
    ll res = 1;
    x = x % mod;
    while (y > 0) {
        if (y % 2 == 1) {
            res = 1LL * res * x % mod;
        }
        x = 1LL * x * x % mod;
        y /= 2;
    }
    res = 1LL * res * x % mod;
    return res;
}

int countReplacement(int n, int g[]) {
	if (!valid(n, g)) {
		return 0;
	}
	ll mult = n;
	vector <ll> saves;
	for (ll 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;
	ll sz = saves.size();
	ll res = 1;
	for (ll i = 0;i < saves.size();i++) {
		ll iter = saves[i] - curr - 1;
		if (iter == 0) {
			sz--;
            curr = saves[i];
			continue;
		}
		res = (res * poww(sz, iter)) % 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