Submission #899253

#	Time	Username	Problem	Language	Result	Execution time	Memory
899253		aqxa	Gondola (IOI14_gondola)	C++17	100 / 100	69 ms	6740 KiB

gondola

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long; 

#include "gondola.h"

int valid(int n, int a[]) {
  	set<int> st; 
	set<int> xs; 
	for (int i = 0; i < n; ++i) {
		if (a[i] <= n) {
			st.insert((a[i] - i + n) % n); 
		}
		if (xs.find(a[i]) != xs.end()) return 0; 
		xs.insert(a[i]); 
	}
	return (st.size() > 1 ? 0 : 1); 
}

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

int replacement(int n, int a[], int ans[]) {
	int v = 1; 
	for (int i = 0; i < n; ++i) {
		if (a[i] <= n) {
			v = (a[i] - i + n) % n; 
		}
	}
	vector<int> b(n); 
	for (int i = 0; i < n; ++i) {
		b[i] = (v + i + n) % n; 
		if (b[i] == 0) b[i] = n; 
	}
	set<pair<int, int>> xs; 
	for (int i = 0; i < n; ++i) {
		if (a[i] > n) xs.insert({a[i], i}); 
	}

	int l = 0, last = n; 
	for (auto [x, p]: xs) {
		while (b[p] < x) {
			ans[l++] = b[p]; 
			b[p] = ++last; 
		}
	}

	// for (int i = 0; i < l; ++i) {
	// 	cout << ans[i] << " \n"[i + 1 == l]; 
	// }

  	return l;
}

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

const int M = 1e9 + 9; 

ll pw(ll x, ll e) {
	ll res = 1; 
	ll cur = x; 
	for (int b = 0; b < 30; ++b) {
		if ((1LL << b) & e) {
			res = (res * cur) % M; 
		}
		cur = (cur * cur) % M; 
	}
	return res; 
}

int countReplacement(int n, int a[]) {
  	if (!valid(n, a)) return -1; 
	int ok = 0, v = 1; 
	ll cp = 0; 
	set<ll> st; 
	for (int i = 0; i < n; ++i) {
		if (a[i] <= n) {
			v = (a[i] - i + n) % n; 
			ok = 1; 
		} else {
			cp++; 
			st.insert(a[i]); 
		}
	}
	ll ans = 1; 

	ll last = n; 
	for (ll x: st) {
		ll cnt = x - last - 1; 
		ans = (ans * (pw(cp, cnt))) % M; 
		cp--; 
		last = x; 
	}

	if (!ok) ans = (ans * n) % M; 

	return (int) (ans % M); 
}

// int32_t main() {
// 	ios::sync_with_stdio(false);
// 	cin.tie(nullptr);
	
// 	int t; 
// 	cin >> t; 
// 	while (t--) {
// 		int n; 
// 		cin >> n; 
// 		int a[n]; 
// 		for (int i = 0; i < n; ++i) cin >> a[i]; 
// 		cout << countReplacement(n, a) << "\n";
// 	}
 
// 	return 0; 
// }	 

Compilation message (stderr)

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:73:14: warning: variable 'v' set but not used [-Wunused-but-set-variable]
   73 |  int ok = 0, v = 1;
      |              ^

• 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