| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 705821 | penguin133 | 곤돌라 (IOI14_gondola) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
//#include "gondola.h"
//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int valid(int n, int inputSeq[])
{
for(int i=1;i<n;i++){
if(inputSeq[i] - inputSeq[i-1] != 1 && (inputSeq[i-1] != n || inputSeq[i] != 1))return 0;
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
vector <pi> stuf;
int rot = 0;
for(int i=0;i<n;i++){
if(gondolaSeq[i] <= n)rot = gondolaSeq[i] - i - 1;
}
if(rot < 0)rot += n;
for(int i=0;i<n;i++){
if(gondolaSeq[i] > n){
int tmp = i + rot + 1;
if(tmp > n)tmp -= n;
stuf.push_back({gondolaSeq[i], tmp});
}
}
sort(stuf.begin(), stuf.end());
int prv = n;
int in = 0;
for(auto [i, j] : stuf){
replacementSeq[in++] = j;
prv++;
for(int x = prv + 1; x <= i; x++)replacementSeq[in++] = x - 1;
prv = i;
}
return in;
}
//----------------------
const long long mod = (int)1e9 + 9;
long long expo(long long a, long long b){
long long ans = 1LL;
while(b){
if(b&1ll)ans *= a, ans %= mod;
a *= a, a %= mod;
b >>= 1LL;
}
return ans;
}
int countReplacement(int n, int inputSeq[])
{
vector <int> stuf;
int rot = -1;
for(int i=0;i<n;i++){
if(inputSeq[i] <= n){
int tmp = inputSeq[i] - i - 1;
if(tmp < 0)tmp += n;
if(rot == -1)rot = tmp;
else if(rot != tmp)return 0;
}
}
for(int i=0;i<n;i++){
if(inputSeq[i] > n)stuf.push_back(inputSeq[i]);
}
sort(stuf.begin(), stuf.end());
long long ans = 1, cur = n;
for(int i=1;i<(int)stuf.size();i++)if(stuf[i] == stuf[i-1])return 0;
for(int i=0;i<(int)stuf.size();i++){
ans *= expo((int)stuf.size() - i, stuf[i] - cur - 1);
ans %= mod;
cur = stuf[i];
}
return ans;
}