Submission #1276844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276844		zyb_txdy	Lollipop (POI11_liz)	C++17	0 / 100	218 ms	27316 KiB

liz

#include <bits/stdc++.h>
#define ll long long
#define mid ((l + r) >> 1)
#define lowbit(x) (x & -x)

using namespace std;

constexpr int N = 1e6 + 5;

int n, m, sum, pos;
int a[N], suf[N], buc[N << 1];
char s[N];

void Solve() {
	int x;
	cin >> x;
	
	if (x > sum) {
		cout << "NIE\n";
		return;
	} else if (~buc[x]) {
		cout << "1 " << buc[x] << '\n';
		return;
	} else if (x == 1) {
		if (pos) {
			cout << pos << ' ' << pos << '\n';
		} else {
			cout << "NIE\n";
		}
		return;
	}
	
	int p = buc[x - 1];
	if (suf[1] < suf[p + 1]) {
		cout << suf[1] + 2 << ' ' << p + suf[1] + 1 << '\n';
	} if (suf[1] >= suf[p + 1] && p + suf[p + 1] < n) {
		cout << suf[p + 1] + 1 << ' ' << p + suf[p + 1] + 1 << '\n';
	} else {
		cout << "NIE\n";
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	
	cin >> n >> m >> s + 1;
	for (int i = 1; i <= n; ++i) {
		a[i] = 1 + (s[i] == 'T');
	}
	
	for (int i = n; i > 0; --i) {
		if (a[i] == 2) {
			suf[i] = suf[i + 1] + 1;
		}
	}
	fill(buc, buc + 2 * n + 1, -1);
	for (int i = 1; i <= n; ++i) {
		sum += a[i];
		buc[sum] = i;
		if (a[i] == 1) {
			pos = i;
		}
	}
	
	while (m--) {
		Solve();
	}
	
	return 0;
}

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