| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 160687 | 2019-10-29T10:33:52 Z | GioChkhaidze | Gondola (IOI14_gondola) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h>
#include "gondola.h"
#define F first
#define S second
using namespace std;
bool f[1e6+6],F[1e6+6];
int Gondol[250003];
pair < int , int > a[250003];
long long mod=1e9+9;
int valid(int n, int inputSeq[]) {
int idx=-1;
for (int i=0; i<n; i++)
if (!f[inputSeq[i]]) f[inputSeq[i]]=1;
else return 0;
for (int i=0; i<n; i++)
if (inputSeq[i]<=n) { idx=i; break; }
if (idx==-1) return 1;
int x=inputSeq[idx];
for (int i=idx+1; ; i++) {
x++;
if (x>n) x-=n;
if (i==n) i-=n;
if (i==idx) break;
if (inputSeq[i]<=n && inputSeq[i]!=x) return 0;
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
int l=0,M=0,idx=-1;
for (int i=0; i<n; i++)
if (gondolaSeq[i]<=n) { idx=i; break; }
for (int i=0; i<n; i++)
a[i].F=gondolaSeq[i],a[i].S=i;
sort(a,a+n);
if (idx==-1) {
for (int i=0; i<n; i++)
Gondol[i]=i+1;
}
else {
int x=gondolaSeq[idx];
Gondol[idx]=x;
for (int i=idx+1; ; i++) {
x++;
if (x>n) x-=n;
if (i==n) i-=n;
if (i==idx) break;
Gondol[i]=x;
}
}
int last=n;
for (int i=0; i<n; i++) {
if (a[i].F<=n) continue;
int id=a[i].S;
replacementSeq[l++]=Gondol[id];
for (int j=last+1; j<a[i].F; j++)
replacementSeq[l++]=j;
last=a[i].F;
}
return l;
}
long long int po(long long a,long long b) {
long long int res=1;
while (b>0) { if (b%2) res=(res*a)%mod; a=(a*a)%mod; b/=2; }
return res;
}
int countReplacement(int n, int inputSeq[]) {
if (!valid(n,inputSeq)) return 0;
sort(inputSeq,inputSeq+n);
long long int ANS=1,last=n;
if (inputSeq[0]>n) ANS=(ANS*n)%mod;
for (int i=0; i<n; i++) {
if (inputSeq[i]<=n) continue;
ANS=(ANS*po(n-i,inputSeq[i]-last-1))%mod;
last=inputSeq[i];
}
return ANS;
}