Submission #1102899

#TimeUsernameProblemLanguageResultExecution timeMemory
1102899alexander707070Gondola (IOI14_gondola)C++14
55 / 100
14 ms8272 KiB
#include<bits/stdc++.h> #include "gondola.h" #define MAXN 500007 using namespace std; const long long mod=1e9+9; int n,pos; int s[MAXN],last,maxs,where[MAXN],val[MAXN]; bool li[MAXN],dali; long long ways; int valid(int N, int inputSeq[]){ n=N; int mins=1; for(int i=1;i<=n;i++){ s[i]=inputSeq[i-1]; s[i+n]=s[i]; if(s[i]<s[mins]){ mins=i; } } for(int i=mins;i<mins+n;i++){ if(s[i]<=n and s[i]!=s[mins]+i-mins)return 0; if(s[i]>n){ if(li[s[i]])return 0; li[s[i]]=true; } } return 1; } int replacement(int N, int gondolaSeq[], int replacementSeq[]){ n=N; maxs=1; for(int i=1;i<=n;i++){ s[i]=gondolaSeq[i-1]; if(s[i]>s[maxs])maxs=i; if(s[i]<=n)pos=i; where[s[i]]=i; } if(pos==0){ for(int i=1;i<=n;i++)val[i]=i; }else{ for(int i=pos;i<=n;i++)val[i]=s[pos]+i-pos; for(int i=1;i<pos;i++)val[i]=val[n]+i; for(int i=1;i<=n;i++){ if(val[i]>n)val[i]-=n; } } for(int i=n+1;i<=s[maxs];i++){ if(where[i]==0){ replacementSeq[i-n-1]=val[maxs]; val[maxs]=i; }else{ replacementSeq[i-n-1]=val[where[i]]; val[where[i]]=i; } } return s[maxs]-n; } long long power(long long a,int b){ if(b==0)return 1; if(b==1)return a; if(b==2)return (a*a)%mod; if(b%2==0)return power(power(a,b/2),2); return (power(power(a,b/2),2)*a)%mod; } int countReplacement(int N, int inputSeq[]){ n=N; for(int i=1;i<=n;i++){ s[i]=inputSeq[i-1]; } sort(s+1,s+n+1); ways=1; last=n; for(int i=1;i<=n;i++){ if(s[i]<=n)continue; ways*=power(n-i+1,s[i]-last); last=s[i]; } return ways; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...