Submission #1033119

#TimeUsernameProblemLanguageResultExecution timeMemory
1033119c2zi6Gondola (IOI14_gondola)C++14
75 / 100
26 ms5580 KiB
#define _USE_MATH_DEFINES #include <bits/stdc++.h> #define ff first #define ss second #define pb push_back #define all(a) (a).begin(), (a).end() #define replr(i, a, b) for (int i = int(a); i <= int(b); ++i) #define reprl(i, a, b) for (int i = int(a); i >= int(b); --i) #define rep(i, n) for (int i = 0; i < int(n); ++i) #define mkp(a, b) make_pair(a, b) using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> PII; typedef vector<int> VI; typedef vector<PII> VPI; typedef vector<VI> VVI; typedef vector<VVI> VVVI; typedef vector<VPI> VVPI; typedef pair<ll, ll> PLL; typedef vector<ll> VL; typedef vector<PLL> VPL; typedef vector<VL> VVL; typedef vector<VVL> VVVL; typedef vector<VPL> VVPL; template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;} template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;} #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template<class T> using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #include "gondola.h" int valid(int n, int inputSeq[]) { VI a; rep(i, n) { if (inputSeq[i] <= n) { int start = i - inputSeq[i] + 1; if (start < n) start += n; replr(i, start, start+n-1) a.pb(inputSeq[i%n]); break; } } if (a.size() == 0) { rep(i, n) a.pb(inputSeq[i]); } set<int> st; for (int x : a) st.insert(x); if (st.size() != a.size()) return false; rep(i, n) { if (a[i] <= n) { if (a[i] != i+1) return false; } } return true; } //---------------------- int replacement(int n, int inputSeq[], int replacementSeq[]) { VI a; rep(i, n) { if (inputSeq[i] <= n) { int start = i - inputSeq[i] + 1; if (start < n) start += n; replr(i, start, start+n-1) a.pb(inputSeq[i%n]); break; } } if (a.size() == 0) { rep(i, n) a.pb(inputSeq[i]); } for (int& x : a) x--; int mx = 0; VI idx(250'000, -1); rep(i, n) { setmax(mx, a[i]); idx[a[i]] = i; } VI ans; map<int, int> cur; rep(i, n) if (idx[i] == -1) { cur[i] = i; } replr(i, n, mx) { if (idx[i] == -1) { auto it = cur.begin(); ans.pb(it->ss); it->ss = i; } else { auto it = cur.lower_bound(idx[i]); ans.pb(it->ss); it->ss = i; cur.erase(it); } } rep(i, ans.size()) replacementSeq[i] = ans[i]+1; return ans.size(); } //---------------------- const ll MOD = 1e9 + 9; int countReplacement(int n, int inputSeq[]) { VI a; rep(i, n) { if (inputSeq[i] <= n) { int start = i - inputSeq[i] + 1; if (start < n) start += n; replr(i, start, start+n-1) a.pb(inputSeq[i%n]); break; } } if (a.size() == 0) { rep(i, n) a.pb(inputSeq[i]); } set<int> st; for (int x : a) st.insert(x); if (st.size() != a.size()) return 0; rep(i, n) if (a[i] <= n && a[i] != i+1) return 0; for (int& x : a) x--; int mx = 0; rep(i, n) setmax(mx, a[i]); VI ka(mx+1); ll cur = 0; rep(i, n) { ka[a[i]] = true; if (a[i] >= n) cur++; } ll ans = 1; replr(i, n, mx) { if (ka[i]) cur--; else { ans *= cur; ans %= MOD; } } 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...