Submission #401911

#TimeUsernameProblemLanguageResultExecution timeMemory
401911idontreallyknowVođe (COCI17_vode)C++17
72 / 120
3089 ms196804 KiB
#include <bits/stdc++.h> using namespace std; struct segtree{ typedef int T; T base = 0; T comb(T a, T b) { return a+b; } int n; vector<T> v; segtree(int x): n(x) { v.resize(2*n+5); } void update(int i, T x) { i+=n; v[i] = x; for (i /= 2; i >= 1; i /= 2) { v[i] = comb(v[2*i], v[2*i+1]); } } T get(int l, int r) { T ans = base; for (l+=n, r+=n; l <= r; l/=2, r/=2) { if (l%2) ans = comb(ans, v[l++]); if ((r+1)%2) ans = comb(ans, v[r--]); } return ans; } void build(vector<T> &x) { for (int q = 0; q < (int)x.size(); q++) { v[q+n] = x[q]; } for (int q = n-1; q >= 1; q--) { v[q] = comb(v[2*q], v[2*q+1]); } } }; vector<segtree> st(5005,segtree(5005)); int a[5005]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n,m,k; cin >> n >> m >> k; for (int q = 0; q < n; q++) cin >> a[q]; for (int q = 0; q < n; q++) st[q].update(m,1-a[q]); for (int q = m-1; q >= 0; q--) { for (int w = 0; w < n; w++) { int e = w == n-1 ? 0 : w+1; int lo = q+1, hi = min(q+k,m); int z = st[e].get(lo,hi); bool win = false; if (a[e] == 1 && z > 0) win = true; if (a[e] == 0 && z < hi-lo+1) win = true; int res = win ? a[e] : 1 - a[e]; st[w].update(q,res); } } for (int q = 0; q < n; q++) { int w = q == 0 ? n-1 : q-1; cout << st[w].get(0,0) << ' '; } cout << '\n'; return 0; }
#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...