256142026-02-23 16:47:42GeneratrollSzorzatország csapata (40 pont)cpp17Accepted 40/4010ms1612 KiB
#include <bits/stdc++.h>
using namespace std;
struct S {
	int c2;
	int s;
	int l;
	int r;
};
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	vector<int> v(n);
	vector<int> p2(n + 1, 0);
	vector<int> pn(n + 1, 0);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
		p2[i + 1] = p2[i] + (abs(v[i]) == 2 ? 1 : 0);
		pn[i + 1] = pn[i] + (v[i] < 0 ? 1 : 0);
	}
	S b = {(abs(v[0]) == 2 ? 1 : 0), (v[0] > 0 ? 1 : (v[0] < 0 ? -1 : 0)), 1, 1};
	auto u = [&](int l, int r, bool z) {
		if (l < 1 || r > n || l > r) {
			return;
		}
		S c;
		if (z) {
			c = {0, 0, l, r};
		} else {
			int cn = pn[r] - pn[l - 1];
			int s = (cn % 2 == 0) ? 1 : -1;
			int c2 = p2[r] - p2[l - 1];
			c = {c2, s, l, r};
		}
		bool btr = false;
		if (c.s != b.s) {
			btr = c.s > b.s;
		} else if (c.s == 1) {
			btr = c.c2 > b.c2;
		} else if (c.s == -1) {
			btr = c.c2 < b.c2;
		}
		if (btr) {
			b = c;
		}
	};
	int lz = -1;
	for (int i = 0; i <= n; i++) {
		if (i == n || v[i] == 0) {
			int l1 = lz + 2;
			int r1 = i;
			if (l1 <= r1) {
				int cn = pn[r1] - pn[l1 - 1];
				if (cn % 2 == 0) {
					u(l1, r1, false);
				} else {
					int f = -1;
					int m = -1;
					for (int k = l1; k <= r1; k++) {
						if (v[k - 1] < 0) {
							if (f == -1) {
								f = k;
							}
							m = k;
						}
					}
					u(f + 1, r1, false);
					u(l1, m - 1, false);
					u(l1, r1, false);
				}
			}
			if (i < n) {
				u(i + 1, i + 1, true);
			}
			lz = i;
		}
	}
	cout << b.l << ' ' << b.r << '\n';
	return 0;
}

SubtaskSumTestVerdictTimeMemory
base40/40
1Accepted0/01ms316 KiB
2Accepted0/08ms1588 KiB
3Accepted1/11ms316 KiB
4Accepted1/11ms316 KiB
5Accepted1/11ms316 KiB
6Accepted1/11ms316 KiB
7Accepted1/11ms316 KiB
8Accepted2/21ms316 KiB
9Accepted2/21ms316 KiB
10Accepted3/39ms1608 KiB
11Accepted3/39ms1608 KiB
12Accepted3/38ms1612 KiB
13Accepted4/410ms1588 KiB
14Accepted4/48ms1588 KiB
15Accepted4/48ms1588 KiB
16Accepted5/59ms1612 KiB
17Accepted5/58ms1612 KiB