# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
432906 | REALITYNB | Gondola (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>
#include "gondola.h"
using namespace std;
int valid(int n ,int* a){
set<int> el ;
for(int i=0;i<n;i++) el.insert(a[i]) ;
if(el.size()!=n) return 0 ;
bool flg= 0 ;
for(int i=0;i<n;i++){
if(a[i]>n) continue;
for(int j=i;j<n+i;j++){
if(a[j%n]>n) continue ;
if(a[j%n]==((a[i]+j-i)<=n?a[i]+j-i:a[i]+j-i-n)) continue ;
return 0;
}
break ;
}
return 1 ;
}
int replacement(int n , int* a , int* ans){
/* map<int,int> occ ;
for(int i=0;i<n;i++) occ[a[i]]=i ;
int res = 0 ;
int start = n+1 , mx = 0 ;
for(int i=0;i<n;i++) mx =max(mx,a[i]) ;
if(mx<=n) return 0 ;
int i = 0 ;
int j= 0;
while(1){
if(occ.count(start)==0){
ans[i]=j;
}
else{
ans[i]=
}
if(start==mx) break ;
++start,++i ;
}
*/
return 1;
}
int countReplacement(int n,int* a){
const int md = 1e9+9 ;
if(valid(n,a)==0) return 0 ;
#define int long long
int spots = 0 ;
for(int i=0;i<n;i++) spots+=(a[i]>n) ;
int ans = (spots==n?n:1), mx = 0 ;
for(int i=0;i<n;i++) mx = max(mx,a[i]) ;
set<int> vis ;
for(int i=0;i<n;i++) vis.insert(a[i]) ;
for(int i=n+1;i<=mx;i++){
if(vis.count(i)) --spots ;
else ans*=spots ;
ans%=md ;
}
#undef int
int hey = ans ;
return hey;
}