Submission #793017

#TimeUsernameProblemLanguageResultExecution timeMemory
793017MODDIGondola (IOI14_gondola)C++17
100 / 100
17 ms3120 KiB
#include "gondola.h" //#include "grader.cpp" #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair typedef long long ll; typedef pair<long long, long long> pll; typedef pair<int,int> pii; typedef vector<int> vi; typedef vector<ll> vl; int valid(int n, int inputSeq[]) { int pos = -1; for(int i = 0; i < n; i++){ if(inputSeq[i] == 1){ pos = i; break; } } bool seq = true; int at = 1, lim = pos; while(pos < n){ if(inputSeq[pos] == at){ pos++; at++; } else{ seq = false; break; } } if(!seq) return 0; pos = 0; while(pos < lim){ if(inputSeq[pos] == at){ pos++; at++; } else{ seq = false; break; } } if(!seq) return 0; return 1; } int replacement(int n, int gondolaSeq[], int replacementSeq[]) { int pos = -1; for(int i = 0; i < n; i++){ if(gondolaSeq[i] >= 1 && gondolaSeq[i] <= n){ pos = i; break; } } if(pos == -1){ vector<pii> arr(n); for(int i = 0; i < n; i++){ arr[i] = mp(gondolaSeq[i], i); } sort(arr.begin(), arr.end()); int j = 0, rez = 0, here = 1, at = n + 1; int pos = arr[0].second, need[n]; for(int i = pos; i < n; i++) need[i] = here++; for(int i = 0; i < pos; i++) need[i] = here++; for(int i = 0; i < (int)arr.size(); i++){ int where = arr[i].second, val = arr[i].first; replacementSeq[j++] = need[where]; rez++; while(at < val){ replacementSeq[j++] = at++; rez++; } at++; } return rez; } else{ int need[n]; bool done[n+1]; memset(done, false, sizeof done); int at = gondolaSeq[pos]; while(at <= n){ at++; pos++; pos%=n; } int here = 1; for(int i = pos; i < n; i++) need[i] = here++; for(int i = 0; i < pos; i++) need[i] = here++; vector<pii> arr; for(int i = 0; i < n; i++){ if(need[i] == gondolaSeq[i]) done[need[i]] = true; else{ arr.pb(mp(gondolaSeq[i], i)); } } sort(arr.begin(), arr.end()); at = n + 1; int j = 0, rez = 0; for(int i = 0; i < (int)arr.size(); i++){ int where = arr[i].second, val = arr[i].first; replacementSeq[j++] = need[where]; rez++; while(at < val){ replacementSeq[j++] = at++; rez++; } at++; } return rez; } } const int mod = 1000000009; int mul(ll a, ll b){ int res = (a*b) % mod; if(res < 0) res += mod; return res; } int pow(int a, int b){ int res = 1; while(b){ if(b&1){ b--; res = mul(res, a); } else{ b >>= 1; a = mul(a,a); } } return res; } int countReplacement(int n, int inputSeq[]) { //int checker = valid(n, inputSeq); vector<pii> arr; int pos = -1; for(int i = 0; i < n; i++){ arr.pb(mp(inputSeq[i], i)); if(inputSeq[i] >= 1 && inputSeq[i] <= n) pos = i; } if(pos != -1){ int at = inputSeq[pos]; while(at <= n){ at++; pos++; pos%=n; } int skipped = 0; at=1; bool ok = true; for(int i = pos; i < n; i++){ if(inputSeq[i] == at+skipped){ at++; skipped = 0; } else if(inputSeq[i] <= n && at + skipped > inputSeq[i]){ ok = false; } else skipped++; } //cout<<"OK: "<<ok<<endl; if(!ok) return 0; } ll ways = 1; if(pos == -1) ways = n; vi niz; for(int i = 0; i < n; i++) if(inputSeq[i] > n) niz.pb(inputSeq[i]); sort(niz.begin(), niz.end()); int sz = (int)niz.size(), last = n; for(int i : niz){ ways = mul(ways, pow(sz, i - last - 1)); last = i; sz--; } 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...