| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1215819 | mayac | Gondola (IOI14_gondola) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;
int valid(int n, int v[]) {
set<int> s;
for (int i = 0; i < n; i++) {
//cout << i << " ";
if (v[i]<=n&&v[i] - 1 != (v[0] - 1 + i) % n)return 0;
if (s.find(v[i]) != s.end())return 0;
s.insert(v[i]);
}
return 1;
}
int replacement(int n, int tmp[], int ans[]) {
int l = 0, t = -1;
priority_queue < pair<int, int>> pq;
set<int> s;
for (int i = 0; i < n; i++) {
l = max(l, tmp[i]);
s.insert(i);
if (tmp[i] <= n) {
t = i;
s.erase(i);
}
else {
pq.push({ -tmp[i],i });
}
}
vector<int> v(n);
l -= n;
if (t == -1) {
for (int i = 0; i < n; i++)v[i] = i + 1;
}
else {
//cout<<t<<"\n";
for (int i = 0; i < n; i++) {
v[(i + t) % n] = ((tmp[t] - 1 + i) % n) + 1;
//cout<<v[((i+t)%n)]<<" "<<tmp[((i+t)%n)]<<"\n";
}
}
for (int i = 0; i < l; i++) {
int m = -pq.top().first, ind = pq.top().second;
if (m == i + n + 1) {
pq.pop();
s.erase(ind);
ans[i] = v[ind];
}
else {
ind = *(s.begin());
ans[i] = v[ind];
v[ind] = n + i + 1;
}
}
return l;
return 2;
}
using ll = long long;
const long long mod = 1000000009;
ll powm(ll a, ll b) {
if (b == 0)return 1;
if (b % 2 == 0) {
return powm((a * a) % mod, b / 2)%mod;
}
return (a*powm((a * a) % mod, b / 2))%mod;
}
int countReplacement(int n, int v[]) {
if (!valid(n, v))return 0;
vector<int> sub(250001,0);
ll last=0, ans = n,c=0;
for (int i = 0; i < n; i++) {
if (v[i] > n) {
sub[v[i]]=-1;
c++;
}else ans=1;
}
for(ll i=n+1;i<=250000&&c>1;i++){
c+=sub[i];
if(sub[i]==-1)i++;else{
ans*=c;
ans%=mod;
}
}
return ans;
}