# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
411984 | losmi247 | Gondola (IOI14_gondola) | C++14 | 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>
#include "gondola.h"
using namespace std;
typedef long long ll;
const int N = 1e5+34;
const int mod = 1000000009;
int n,a[N];
map <int,int> pos,bio;
int treba[N];
int valid(int br,int *inputseq){
n = br;
for(int i = 1; i <= n; i++) a[i] = inputseq[i-1];
for(int i = 1; i <= n; i++){
if(a[i] <= n) pos[a[i]] = i;
if(bio[a[i]]) return 0;
bio[a[i]] = 1;
}
int lst = 0;
bool ok = 1;
for(int i = 1; i <= n; i++){
if(!pos[i]) continue;
if(!lst){
lst = i;
continue;
}
if(pos[lst] < pos[i]){
if(pos[i]-pos[lst] != i-lst){
ok = 0;
break;
}
}
else{
if(pos[lst]-pos[i]-1 != lst-1+n-i){
ok = 0;
break;
}
}
lst = i;
}
return ok;
}
int replacement(int br,int *gondolaSeq,int *replacementSeq){
n = br;
for(int i = 1; i <= n; i++) a[i] = gondolaSeq[i-1];
for(int i = 1; i <= n; i++){
if(a[i] <= n){
treba[i] = a[i];
}
else if(i > 1){
if(treba[i-1] == n) treba[i] = 1;
else if(treba[i-1]) treba[i] = treba[i-1]+1;
}
}
for(int i = n; i >= 1; i--){
if(treba[i]) continue;
if(treba[i+1] == 1) treba[i] = n;
else treba[i] = treba[i+1]-1;
}
bool svi = 1;
for(int i = 1; i <= n; i++){
if(a[i] <= n) svi = 0;
}
if(svi){
for(int i = 1; i <= n; i++){
treba[i] = i;
}
}
for(int i = 1; i <= n; i++){
assert(1 <= treba[i] && treba[i] <= n);
}
vector <pair<int,int>> v;
for(int i = 1; i <= n; i++){
if(treba[i] != a[i]) v.push_back({a[i],treba[i]});
}
sort(v.begin(),v.end());
/*cout << v.size() << " evo" << endl;
for(auto f : v){
cout << f.first << " " << f.second << endl;
}
cout << endl;*/
int cnt = 0,stigo = n;
for(auto f : v){
for(int j = stigo; j < f.first; j++) replacementSeq[cnt++] = (j == stigo ? f.second : j);
stigo = f.first;
}
return cnt;
}
ll fp(ll x,ll y){
if(y == 0){
return 1;
}
ll p = fp(x,y/2);
p = (p*p)%mod;
if(y&1){
p = (p*x)%mod;
}
return p;
}
ll countReplacement(int br,int *inputSeq){
n = br;
for(int i = 1; i <= n; i++) a[i] = inputSeq[i-1];
if(!valid(br,inputSeq)){
return 0;
}
for(int i = 1; i <= n; i++){
if(a[i] <= n){
treba[i] = a[i];
}
else if(i > 1){
if(treba[i-1] == n) treba[i] = 1;
else if(treba[i-1]) treba[i] = treba[i-1]+1;
}
}
for(int i = n; i >= 1; i--){
if(treba[i]) continue;
if(treba[i+1] == 1) treba[i] = n;
else treba[i] = treba[i+1]-1;
}
bool svi = 1;
for(int i = 1; i <= n; i++){
if(a[i] <= n) svi = 0;
}
if(svi){
for(int i = 1; i <= n; i++){
treba[i] = i;
}
}
for(int i = 1; i <= n; i++){
assert(1 <= treba[i] && treba[i] <= n);
}
vector <pair<ll,ll>> v;
for(int i = 1; i <= n; i++){
if(treba[i] != a[i]) v.push_back({a[i],treba[i]});
}
sort(v.begin(),v.end());
ll k = v.size();
ll sol = 1;
ll prosli = n;
for(ll i = 0; i < v.size(); i++){
if(i == 0){
ll pom = fp(k,v[i].first-prosli-1);
sol *= pom;
sol %= mod;
prosli = v[i].first;
}
else{
ll pom = fp(k-i,v[i].first-prosli-1);
sol *= pom;
sol %= mod;
prosli = v[i].first;
}
}
if(svi){
ll fak = 1;
for(ll i = 2; i <= n; i++){
fak *= i;
fak %= mod;
}
sol *= fak;
sol %= mod;
}
return sol;
}
/*int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int a;
cin >> a;
int *niz = (int*)malloc(sizeof(int)*a);
for(int i = 0; i < a; i++) cin >> niz[i];
cout << valid(a,niz) << endl;
int a;
cin >> a;
int *niz = (int*)malloc(sizeof(int)*a);
for(int i = 0; i < a; i++) cin >> niz[i];
int *drugi = (int*)malloc(sizeof(int)*200);
int len = replacement(a,niz,drugi);
cout << len << endl;
for(int i = 0; i < len; i++){
cout << drugi[i] << " ";
}
cout << endl;
int a;
cin >> a;
int *niz = (int*)malloc(sizeof(int)*a);
for(int i = 0; i < a; i++) cin >> niz[i];
cout << countReplacement(a,niz) << endl;
}*/