aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAnthony Wang2020-10-06 17:29:00 -0500
committerAnthony Wang2020-10-06 17:29:00 -0500
commitac539fe4aa93fc68aff6661c616d3489645896d3 (patch)
tree38320f607e93acbab6dbc6c720c7360d80b2b29c
parentc4e19326d129a01b7447d8b2be523128f8d1e0e3 (diff)
Add garden.cpp
-rw-r--r--08/garden.cpp31
1 files changed, 31 insertions, 0 deletions
diff --git a/08/garden.cpp b/08/garden.cpp
new file mode 100644
index 0000000..bb68420
--- /dev/null
+++ b/08/garden.cpp
@@ -0,0 +1,31 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+using ll = long long;
+using ii = pair<int, int>;
+constexpr int MX = 1e6+5;
+
+int p2[MX] = { 1 };
+
+int main() {
+ if (fopen("in", "r")) freopen("in", "r", stdin), freopen("out", "w", stdout);
+ ios_base::sync_with_stdio(0), cin.tie(0);
+
+ int N, M; cin >> N >> M;
+ string S; cin >> S;
+
+ for (int i = 0; i < N; ++i) p2[i+1] = 2*p2[i]%M;
+
+ int ans = 1, cnt = 0, l = 0, h = 0;
+ for (int i = 0; i < N; ++i) {
+ if (S[i] == 'P') {
+ int a = min(cnt-1, l), b = max(cnt-1, h);
+ if (abs(b-a) == 1) (ans += p2[(N-i-1)/2]+p2[(N-i)/2]-1) %= M;
+ else if (abs(b-a) == 2) (ans += p2[(N-i-(cnt != a))/2]) %= M;
+ }
+ cnt += (S[i] == 'P' ? 1 : -1);
+ l = min(cnt, l), h = max(cnt, h);
+ }
+ cout << ans;
+}