Submission #147776

#TimeUsernameProblemLanguageResultExecution timeMemory
147776karmaGondola (IOI14_gondola)C++14
90 / 100
24 ms2532 KiB
#include <bits/stdc++.h> #include "gondola.h" #define pb emplace_back #define fi first #define se second using namespace std; const int N = int(3e5) + 2; const int M = int(1e6) + 1; const int mod = int(1e9) + 9; int dem[N]; bitset<M> vis; int valid(int n, int p[]) { int mn = 0, res = -1; for(int i = 0; i < n; ++i) { if(p[mn] > p[i]) mn = i; if(++dem[p[i]] > 1) res = 0; } if(p[mn] > n && res == -1) res = 1; for(int i = mn, lim = mn + n; i < lim; ++i) { --dem[p[i % n]]; if(p[i % n] > n || res != -1) continue; if(p[i % n] - p[mn] != i - mn) res = 0; } if(res == -1) res = 1; return res; } typedef pair<int, int> pii; int replacement(int n, int p[], int res[]) { int mn = 0, cnt = 0; vector<int> org(n); vector<pii> v; for(int i = 0; i < n; ++i) { if(p[mn] > p[i]) mn = i; if(p[i] > n) v.pb(i, p[i]); } sort(v.begin(), v.end(), [](const pii& x, const pii& y){ return x.se < y.se; }); for(int i = mn, lim = mn + n; i < lim; ++i) { if(p[mn] > n) org[i - mn] = i - mn + 1; else org[i % n] = (p[mn] + i - mn - 1) % n + 1; } mn = n + 1; for(pii x: v) { res[cnt ++] = org[x.fi]; while(mn < x.se) res[cnt ++] = mn ++; mn = x.se + 1; } return cnt; } int countReplacement(int n, int p[]) { if(!valid(n, p)) return 0; int mx = 0, cnt = 0, res = 1; vis.reset(); for(int i = 0; i < n; ++i) { mx = max(p[i], mx); if(p[i] > n) ++cnt, vis.set(p[i]); } if(*min_element(p, p + n) > n) res = n; for(int i = n + 1; i <= mx; ++i) { if(vis.test(i)) --cnt, vis.flip(i); else res = 1ll * res * cnt % mod; } return res; } // //int n, a[N], cmd, res[N]; // //int main() //{ // ios_base::sync_with_stdio(0); // cin.tie(0), cout.tie(0); // if(fopen("test.inp", "r")) { // freopen("test.inp", "r", stdin); // freopen("test.out", "w", stdout); // } // int nTest; // cin >> nTest; // while(nTest --) { // cin >> cmd >> n; // for(int i = 0; i < n; ++i) cin >> a[i]; // if(cmd == 1) cout << valid(n, a) << '\n'; // else if(cmd == 2) { // int sz = replacement(n, a, res); // for(int i = 0; i < sz; ++i) cout << res[i] << ' '; // cout << '\n'; // } else cout << countReplacement(n, a) << '\n'; // } //}
#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...