제출 #310421

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
310421		Temmie	Linear Garden (IOI08_linear_garden)	C++17	86 / 100	119 ms	1436 KiB

linear_garden

#include <bits/stdc++.h>

typedef long long ll;

ll pow(ll x, ll p, ll m) {
	p %= m;
	ll r = 1;
	while (p) {
		if (p & 1LL) r = (r * x) % m;
		x = (x * x) % m;
		p >>= 1LL;
	}
	return r;
}

void rem(ll& x, ll m) {
	x--;
	if (x == -1LL) x += m;
}

ll add(ll x, ll y, ll m) {
	x += y;
	while (x >= m) x -= m;
	while (x < 0) x += m;
	return x;
}

int main() {
	std::ios::sync_with_stdio(0); std::cin.tie(0);
	
	ll n, m; std::cin >> n >> m;
	std::string s; std::cin >> s;
	ll l = 0, r = 0, now = 0, ans = 0;
	for (ll i = 0; i < n; i++) {
		if (s[i] == 'L') now++, r = std::max(r, now);
		else {
			ll rr = std::max(r, now + 1LL);
			ll rn = n - i - 1LL;
			if (!(rr - l - 1LL))
				ans = add(ans, pow(2LL, rn >> 1LL, m), m),
				ans = add(ans, pow(2LL, (rn + 1LL) >> 1LL, m), m),
				rem(ans, m);
			else if (!(rr - l - 2)) {
				if (now + 1LL == rr - 1LL) ans = add(ans, pow(2LL, (rn + 1LL) >> 1LL, m), m);
				else ans = add(ans, pow(2LL, rn >> 1LL, m), m);
			}
			now--, l = std::min(l, now);
		}
	}
	std::cout << add(ans, 1LL, m) << "\n";
	
}

• Subtask 1: 2 / 2
• Subtask 2: 2 / 2
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 4 / 4
• Subtask 7: 4 / 4
• Subtask 8: 4 / 4
• Subtask 9: 4 / 4
• Subtask 10: 4 / 4
• Subtask 11: 0 / 4
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 0 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5
• Subtask 21: 5 / 5
• Subtask 22: 0 / 5
• Subtask 23: 5 / 5