| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1308299 | Rares | 곤돌라 (IOI14_gondola) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
/**ifstream fin ("date.in");
ofstream fout ("date.out");
#define cin fin
#define cout fout**/
#define int long long
const int MAXN=1e6+10;
const int MOD=1e9+9;
int f[MAXN];
map <int,bool> m;
int valid (int n, int a[]){
int x=-1;
for (int i=n;i>=1;--i){
a[i]=a[i-1];
}
for (int i=1;i<=n;++i){
if (m[a[i]]) return false;
m[a[i]]=1;
if (a[i]>n) continue;
int crt=a[i]-i;
if (crt<0) crt+=n;
if (x==-1){
x=crt;
}
else{
if (x!=crt) return 0;
}
}
return 1;
}
int val[MAXN];
int replacement(int n, int a[], int b[]){
int crt=-1;
for (int i=n;i>=1;--i){
a[i]=a[i-1];
}
for (int i=1;i<=n;++i){
if (a[i]<n){
crt=a[i]-i;
if (crt<0) crt+=n;
}
}
if (crt==-1){
int maxx=0,pcrt=1;
for (int i=1;i<=n;++i){
val[a[i]]=i;
if (maxx<a[i]){
maxx=a[i];
pcrt=i;
}
a[i]=i;
}
for (int i=n+1;i<=maxx;++i){
if (val[i]){
b[i-n-1]=a[val[i]];
a[val[i]]=i;
}
else{
b[i-n-1]=a[pcrt];
a[pcrt]=i;
}
}
return maxx-n;
}
int maxx=0,pcrt=0;
for (int i=1;i<=n;++i){
if (a[i]>maxx){
maxx=a[i];
pcrt=i;
}
if (a[i]>n){
int p=crt+i;
if (p>n) p-=n;
val[a[i]]=i;
a[i]=p;
}
}
for (int i=n+1;i<=maxx;++i){
if (val[i]){
b[i-n-1]=a[val[i]];
a[val[i]]=i;
}
else{
b[i-n-1]=a[pcrt];
a[pcrt]=i;
}
}
return maxx-n;
}
int expr (int x, int e){
int p=1;
while (e){
if (e%2) p=1LL*p*x%MOD;
x=1LL*x*x%MOD;
e>>=1;
}
return p;
}
int countReplacement(int n, int a[]){
if (!valid (n,a)) return 0;
vector <int> v;
for (int i=1;i<=n;++i){
if (a[i]>n) v.push_back(a[i]);
}
int rez=1;
sort (v.begin (),v.end ());
int nra=v.size (),prev=n+1;
for (auto x:v){
int e=x-prev;
rez=1LL*rez*expr (nra,e)%MOD;
nra--;
prev=x+1;
}
return rez;
}