Submission #50686

#	Time	Username	Problem	Language	Result	Execution time	Memory
50686		szawinis	Lollipop (POI11_liz)	C++17	100 / 100	719 ms	123896 KiB

liz

#include <bits/stdc++.h>
using namespace std;
#define fori(i, a, b) for(int i = (int) a; i <= (int) b; ++i)
#define rofi(i, b, a) for(int i = (int) b; i >= (int) a; --i)
#define foreach(tt, a) for(auto &tt: a)
#define all(a) begin(a), end(a)
#define csz(a) (int) a.size()
#define pb push_back
#define epb emplace_back
#define mp make_pair
#define load(a, v) fill(begin(a), end(a), v)
#define load_mem(a, v) memset(a, v, sizeof(a));
#define iostream_optimize() ios::sync_with_stdio(false); cin.tie(0);
using ll = long long;
const ll MOD = 1e9+7, LINF = 1e16+1;
const int INF = 1e9+1;
const double EPS = 1e-10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
const ll P1 = 31, P2 = 37, M1 = 1e9+7, M2 = 1e9+9;

// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// template <typename T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
/* <<<<<<<<<<<<<<<<<<<<<<<<<<<< END TEMPLATE >>>>>>>>>>>>>>>>>>>>>>>>>>> */
const int N = 1e6+2;

int n, q, a[N], sum[N], rev[2*N], nxt[N];
char s[N];

bool valid(int l, int r, int k) {
	return l <= r && l >= 1 && l <= n && r >= 1 && r <= n && (sum[r] - sum[l-1] == k);
}

int main() {
	scanf("%d %d %s", &n, &q, s);
	load_mem(rev, -1);
	load(nxt, INF);
	fori(i, 1, n) {
		a[i] = (s[i-1] == 'T' ? 2 : 1);
		sum[i] = sum[i-1] + a[i];
		rev[sum[i]] = i;
	}
	rofi(i, n, 2) {
		if(a[i] != a[i-1]) nxt[i-1] = i;
		else nxt[i-1] = nxt[i];
	}
	fori(z, 0, q-1) {
		int k; scanf("%d", &k);
		if(k > sum[n]) { printf("NIE\n"); continue; }
		if(rev[k] != -1) { printf("1 %d\n", rev[k]); continue; }

		int i = rev[k+1];
		int l = -1, r = -1;
		if(i == 1) {
			if(valid(nxt[i], nxt[i], k)) l = r = nxt[i];
		} else if(a[1] == 2 && a[i] == 2) {
			if(nxt[i] - i == nxt[1] - 1) {
				if(valid(nxt[1], nxt[i], k)) l = nxt[1], r = nxt[i];
			} else if(nxt[i] - i < nxt[1] - 1) {
				if(valid(nxt[i] - i + 1, nxt[i], k)) l = nxt[i] - i + 1, r = nxt[i];
			} else {
				if(valid(nxt[1] + 1, nxt[1] + i - 1, k)) l = nxt[1] + 1, r = nxt[1] + i - 1;
			}
		} else {
			if(a[1] == 1) l = 2, r = i;
			else if(a[i] == 1) l = 1, r = i-1;
			else assert(false);
		}
		if(l == -1 && r == -1) printf("NIE\n");
		else printf("%d %d\n", l, r);
	}
}

Compilation message (stderr)

liz.cpp: In function 'int main()':
liz.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %s", &n, &q, s);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
liz.cpp:50:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int k; scanf("%d", &k);
          ~~~~~^~~~~~~~~~

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