Submission #1183505

#TimeUsernameProblemLanguageResultExecution timeMemory
1183505Albara_AbdulhafithGondola (IOI14_gondola)C++20
55 / 100
31 ms4680 KiB
#include "gondola.h" #include <map> #include <vector> #include <algorithm> using namespace std; typedef long long ll; const ll modu = ll(1e9) + 9ll; int mod(int x, int n){ return ((x % n) + n) % n; } ll mod(ll x){ return (x % modu); } ll fast(ll base, ll power){ ll ret = 1ll; while(power){ if(power & 1ll){ ret = mod(ret * base); } power >>= 1; base = mod(base * base); } return ret; } int valid(int n, int inputSeq[]) { int mn = n + 1; int id = -1; map<int, int> freq; for(int i = 0; i < n; i++){ if(inputSeq[i] <= n and inputSeq[i] < mn){ mn = inputSeq[i]; id = i; } freq[inputSeq[i]]++; if(freq[inputSeq[i]] > 1){ return 0; } } if(id == -1){ return 1; } for(int i = 0; i < n; i++){ if(inputSeq[(i + id) % n] <= n and inputSeq[(i + id) % n] != mn){ return 0; } mn++; } return 1; } //---------------------- int replacement(int n, int gondolaSeq[], int replacementSeq[]) { int mn = n + 1; int id = -1; int not_used = n + 1; int l = 0; vector<pair<int, int>> v; for(int i = 0; i < n;i++){ if(gondolaSeq[i] <= n and gondolaSeq[i] < mn){ mn = gondolaSeq[i]; id = i; } else if(gondolaSeq[i] > n){ v.push_back(make_pair(gondolaSeq[i], i)); } } sort(v.begin(), v.end()); if(id == -1){ id = 0; } else{ id = mod(id - mn + 1, n); } for(int i = 0; i < int(v.size()); i++){ replacementSeq[l] = mod(v[i].second - id, n) + 1; l++; while(not_used < v[i].first){ replacementSeq[l] = not_used; not_used++; l++; } not_used++; } return l; } //---------------------- int countReplacement(int n, int inputSeq[]) { int mn = n + 1; int id = -1; map<int, int> freq; for(int i = 0; i < n; i++){ if(inputSeq[i] <= n and inputSeq[i] < mn){ mn = inputSeq[i]; id = i; } freq[inputSeq[i]]++; if(freq[inputSeq[i]] > 1){ return 0; } } for(int i = 0; i < n and id != -1; i++){ if(inputSeq[(i + id) % n] <= n and inputSeq[(i + id) % n] != mn){ return 0; } mn++; if(mn > n){ mn = 1; } } //============================================================ ll ans = 1ll; bool check = true; ll not_used = ll(n) + 1ll; vector<ll> v; for(int i = 0; i < n;i++){ if(inputSeq[i] <= n and inputSeq[i] < mn){ check = false; } else if(inputSeq[i] > n){ v.push_back(ll(inputSeq[i])); } } sort(v.begin(), v.end()); if(check){ ans = mod(ans * ll(n)); } ll sz = ll(v.size()); for(ll i = 0ll; i + 1ll < sz; i++){ ans = mod(ans * fast(sz - i, v[i] - not_used) ); not_used = v[i] + 1ll; } return int(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...