Submission #1032095

#TimeUsernameProblemLanguageResultExecution timeMemory
1032095tolbiGondola (IOI14_gondola)C++17
100 / 100
47 ms6812 KiB
#include "gondola.h" #include <bits/stdc++.h> using namespace std; int valid(int n, int inputSeq[]) { map<int,int> mp; int p = -1; for (int i = 0; i < n; ++i) { if (mp[inputSeq[i]]) return 0; mp[inputSeq[i]]++; } for (int i = 0; i < n; i++){ if (inputSeq[i]<=n){ p=i; break; } } if (p==-1) return 1; for (int i = 0; i < n; i++){ if (inputSeq[i]>n) continue; int step = i-p; if (i<p) step = n-p+i; int a = inputSeq[p]-1; a+=step; a%=n; a++; if (inputSeq[i]!=a) return 0; } return 1; } //---------------------- int replacement(int n, int gondolaSeq[], int replacementSeq[]) { pair<int,int> v[n]; for (int i = 0; i < n; ++i) { v[i]={gondolaSeq[i],i}; } sort(v,v+n); int cnt = 0; int p = 0; for (int i = 0; i < n; i++){ if (gondolaSeq[i]<=n){ p=i-gondolaSeq[i]+1; if (p<0) p+=n; break; } } for (int i = 0; i < n; i++){ if (v[i].first<=n) continue; int lel = v[i].second-p+1; if (v[i].second<p) lel = n-p+v[i].second+1; while (cnt<v[i].first-n) { replacementSeq[cnt]=lel; lel=cnt+n+1; cnt++; } } return cnt; } //---------------------- constexpr int MOD = 1e9+9; int fpow(int base, int pow){ int rval = 1; while (pow){ if (pow&1){ rval=(1LL*rval*base)%MOD; } base=(1LL*base*base)%MOD; pow>>=1; } return rval; } int countReplacement(int n, int inputSeq[]) { if (!valid(n,inputSeq)) return 0; pair<int,int> v[n]; int kapali = 0; int ans = n; for (int i = 0; i < n; ++i) { if (inputSeq[i]>n) { kapali++; } v[i]={inputSeq[i],i}; } if (kapali!=n) ans=1; sort(v,v+n); int cnt = 0; for (int i = 0; i < n; i++){ if (v[i].first<=n) continue; int kal = n-i; ans=(1LL*ans*fpow(kal,max(0,v[i].first-n-cnt-1)))%MOD; cnt=v[i].first-n; while (cnt<v[i].first-n) { cnt++; } } return ans; }
#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...