Submission #401909

#	Time	Username	Problem	Language	Result	Execution time	Memory
401909		idontreallyknow	Vođe (COCI17_vode)	C++17	72 / 120	3091 ms	196848 KiB

vode

#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+1)%n;
			int lo = q+1, hi = min(q+k,m);
			int z = st[e].get(lo,hi);
			vector<bool> win(2);
			if (z < hi-lo+1) win[0] = true;
			if (z > 0) win[1] = true;
			int res = win[a[e]] ? a[e] : 1-a[e];
			st[w].update(q,res);
		}
	}
	for (int q = 0; q < n; q++) {
		int w = (q+n-1)%n;
		cout << st[w].get(0,0) << ' ';
	}
	cout << '\n';
	return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 0 / 12
• Subtask 8: 0 / 12
• Subtask 9: 0 / 12
• Subtask 10: 0 / 12