oj.uz

Submission #762014

# Submission time Handle Problem Language Result Execution time Memory
762014 2023-06-20T14:38:22 Z gun_gan Linear Garden (IOI08_linear_garden) C++17
100 / 100
 146 ms 48864 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX = 1e6 + 5;

int dp[MX][3][2][2]; // pos, condition, prefix, last
int N, mod;
string s;

int main() {
      ios_base::sync_with_stdio(0); cin.tie(0);

      cin >> N >> mod >> s;
      
      // P = 1, L = 0
      if(s[0] == 'P') {
            dp[0][0][0][0] = 1;
            dp[0][0][1][1] = 1;
      } else {
            dp[0][0][1][0] = 1;
      }

      for(int i = 0; i + 1 < N; i++) {
            for(int cond = 0; cond < 3; cond++) { // condition
                  for(int p = 0; p < 2; p++) { // prefix
                        for(int lst = 0; lst < 2; lst++) { // last 0 / 1
                              // tarok 0
                              int nx = p & (s[i + 1] == 'L');
                              if(cond == 2 && lst) {  
                                    dp[i + 1][cond][nx][0] += 
                                          dp[i][cond][p][lst];
                                    if(dp[i + 1][cond][nx][0] >= mod) dp[i + 1][cond][nx][0] -= mod;
                              }

                              if(cond == 2 && !lst) {
                                    dp[i + 1][1][nx][0] +=
                                          dp[i][cond][p][lst];
                                    if(dp[i + 1][1][nx][0] >= mod) dp[i + 1][1][nx][0] -= mod;
                              }

                              if(cond == 1 && lst) {
                                    dp[i + 1][cond][nx][0] += 
                                          dp[i][cond][p][lst];
                                    if(dp[i + 1][cond][nx][0] >= mod) dp[i + 1][cond][nx][0] -= mod;
                              }

                              if(cond == 0 && lst) {
                                    dp[i + 1][cond][nx][0] += 
                                          dp[i][cond][p][lst];
                                    if(dp[i + 1][cond][nx][0] >= mod) dp[i + 1][cond][nx][0] -= mod;
                              }

                              if(cond == 0 && !lst) {
                                    dp[i + 1][1][nx][0] += 
                                          dp[i][cond][p][lst];
                                    if(dp[i + 1][1][nx][0] >= mod) dp[i + 1][1][nx][0] -= mod;
                              } 

                              // tarok 1
                              if(p && s[i + 1] == 'L') continue;

                              nx = p & (s[i + 1] == 'P');
                              if(cond == 2 && !lst) {
                                    dp[i + 1][cond][nx][1] += 
                                          dp[i][cond][p][lst];
                                    if(dp[i + 1][cond][nx][1] >= mod) dp[i + 1][cond][nx][1] -= mod;
                              }

                              if(cond == 1 && !lst) {
                                    dp[i + 1][cond][nx][1] += 
                                          dp[i][cond][p][lst];
                                    if(dp[i + 1][cond][nx][1] >= mod) dp[i + 1][cond][nx][1] -= mod;
                              }

                              if(cond == 1 && lst) {
                                    dp[i + 1][2][nx][1] += 
                                          dp[i][cond][p][lst];
                                    if(dp[i + 1][2][nx][1] >= mod) dp[i + 1][2][nx][1] -= mod;
                              }

                              if(cond == 0 && lst) {
                                    dp[i + 1][2][nx][1] += 
                                          dp[i][cond][p][lst];
                                    if(dp[i + 1][2][nx][1] >= mod) dp[i + 1][2][nx][1] -= mod;
                              }

                              if(cond == 0 && !lst) {
                                    dp[i + 1][cond][nx][1] += 
                                          dp[i][cond][p][lst];
                                    if(dp[i + 1][cond][nx][1] >= mod) dp[i + 1][cond][nx][1] -= mod;
                              }
                        }
                  }
            }
      }
      
      int ans = 0;
      for(int cond = 0; cond < 3; cond++) { // condition
            for(int p = 0; p < 2; p++) { // prefix
                  for(int lst = 0; lst < 2; lst++) { // last 0 / 1
                        ans += dp[N - 1][cond][p][lst];
                        if(ans >= mod) ans -= mod;
                  }
            }
      }

      cout << ans << '\n';
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #7
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #8
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #9
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #10
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #11
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 468 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1232 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1364 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3356 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3988 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 15564 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 20096 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 25396 KB Output is correct

Subtask #22
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 30808 KB Output is correct

Subtask #23
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 48864 KB Output is correct
2 Correct 114 ms 48832 KB Output is correct
3 Correct 146 ms 48860 KB Output is correct