제출 #310418

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

linear_garden

#include <bits/stdc++.h>

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

int rem(int& x, int m) {
	x--;
	if (x == -1) x += m;
	return x;
}

int main() {
	std::ios::sync_with_stdio(0); std::cin.tie(0);
	
	int n, m; std::cin >> n >> m;
	std::string s; std::cin >> s;
	int l = 0, r = 0, now = 0, ans = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == 'L') now++, r = std::max(r, now);
		else {
			int rr = std::max(r, now + 1);
			int rn = n - i - 1;
			if (!(rr - l - 1)) ans = (ans + pow(2, rn >> 1, m) + pow(2, (rn + 1) >> 1, m)) % m, rem(ans, m);
			else if (!(rr - l - 2)) {
				if (now + 1 == rr - 1) ans = (ans + pow(2, (rn + 1) >> 1, m)) % m;
				else ans = (ans + pow(2, rn >> 1, m)) % m;
			}
			now--, l = std::min(l, now);
		}
	}
	std::cout << (ans + 1) % 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: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5
• Subtask 22: 0 / 5
• Subtask 23: 0 / 5