oj.uz

Submission #401909

# Submission time Handle Problem Language Result Execution time Memory
401909 2021-05-11T01:16:45 Z idontreallyknow Vođe (COCI17_vode) C++17
72 / 120
 3000 ms 196848 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 196676 KB Output is correct
2 Correct 88 ms 196732 KB Output is correct
3 Correct 96 ms 196672 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 196744 KB Output is correct
2 Correct 89 ms 196848 KB Output is correct
3 Correct 93 ms 196760 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 196704 KB Output is correct
2 Correct 91 ms 196696 KB Output is correct
3 Correct 97 ms 196656 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 196676 KB Output is correct
2 Correct 117 ms 196704 KB Output is correct
3 Correct 105 ms 196684 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 196760 KB Output is correct
2 Correct 118 ms 196736 KB Output is correct
3 Correct 110 ms 196744 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 196764 KB Output is correct
2 Correct 120 ms 196724 KB Output is correct
3 Correct 101 ms 196676 KB Output is correct

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 196756 KB Output is correct
2 Correct 640 ms 196760 KB Output is correct
3 Execution timed out 3073 ms 196788 KB Time limit exceeded

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1332 ms 196688 KB Output is correct
2 Execution timed out 3077 ms 196804 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3066 ms 196672 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3091 ms 196752 KB Time limit exceeded
2 Halted 0 ms 0 KB -