Submission #486471

#	Time	Username	Problem	Language	Result	Execution time	Memory
486471		Alexandruabcde	Linear Garden (IOI08_linear_garden)	C++14	100 / 100	45 ms	16924 KiB

linear_garden

#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 1e6 + 2;

int N, M;
char ch[NMAX];
int dp[NMAX][2][2];
/// 0 -> L; 1 -> P;

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;

    for (int i = 1; i <= N; ++ i)
        cin >> ch[i];
}

void Precalculate () {
    for (int i = 0; i < 2; ++ i )
        for (int j = 0; j < 2; ++ j )
            dp[1][i][j] = dp[0][i][j] = 1;

    for (int i = 2; i <= N; ++ i ) {
        dp[i][0][0] = (1LL * dp[i-1][1][0] + 1LL * dp[i-2][1][1]) % M;
        dp[i][0][1] = (1LL * dp[i-1][1][1]) % M;
        dp[i][1][0] = (1LL * dp[i-1][0][0]) % M;
        dp[i][1][1] = (1LL * dp[i-1][0][1] + 1LL * dp[i-2][0][0]) % M;
    }
}

void Solve () {
    int bef_dublu = 2;
    int dublu = 2;
    int ans = 0;

    for (int i = 1; i <= N; ++ i ) {
        if (ch[i] == 'L') {
            if (ch[i-1] == 'L'){
                bef_dublu = dublu;
                dublu = 0;
            }

            continue;
        }

        if (ch[i-1] == 'P') {
            bef_dublu = dublu;
            dublu = 1;
        }

        if (dublu == 2) {
            if (i == 1)
                ans = (1LL * ans + M + 1LL * dp[N-i+1][0][0] + 1LL * dp[N-i+1][0][1] - 1) % M;
            else ans = (1LL * ans + 1LL * dp[N-i+1][0][1]) % M;
        }

        if (dublu == 1) {
            if (ch[i-1] == 'P') {
                if (bef_dublu == 0)
                    ans = (1LL * ans + 1LL * dp[N-i+1][0][1]) % M;
                else ans = (1LL * ans + M + 1LL * dp[N-i+1][0][1] + 1LL * dp[N-i+1][0][0] - 1) % M;
            }
            else ans = (1LL * ans + dp[N-i+1][0][1]) % M;
        }
    }

    cout << (ans+1) % M << '\n';
}

int main () {
    Read();
    Precalculate();
    Solve();

    return 0;
}

• 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: 4 / 4
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 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: 5 / 5
• Subtask 23: 5 / 5