Submission #1309392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309392		khang2010	Linear Garden (IOI08_linear_garden)	C++20	100 / 100	49 ms	36732 KiB

linear_garden

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

inline pair<int,int> next_state(int hi, int cur, char c) {
    int ncur = cur + (c == 'L' ? 1 : -1);
    int nhi = hi;

    if (ncur < 0) {
        nhi = hi + 1;
        ncur = 0;
    } else {
        nhi = max(hi, ncur);
    }

    if (nhi > 2) return {-1, -1};
    return {nhi, ncur};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    ll M;
    string S;
    cin >> N >> M >> S;

    // ways[len][hi][cur]
    static int ways[1000001][3][3];

    // base: len = 0
    for (int h = 0; h <= 2; h++)
        for (int c = 0; c <= h; c++)
            ways[0][h][c] = 1;

    // build DP
    for (int len = 1; len <= N; len++) {
        for (int h = 0; h <= 2; h++) {
            for (int c = 0; c <= h; c++) {
                ll v = 0;
                for (char ch : {'L', 'P'}) {
                    auto [nh, nc] = next_state(h, c, ch);
                    if (nh != -1)
                        v += ways[len - 1][nh][nc];
                }
                ways[len][h][c] = v % M;
            }
        }
    }

    // compute rank
    ll rank = 1;
    int hi = 0, cur = 0;

    for (int i = 0; i < N; i++) {
        int rem = N - i - 1;

        if (S[i] == 'P') {
            auto [nh, nc] = next_state(hi, cur, 'L');
            if (nh != -1)
                rank = (rank + ways[rem][nh][nc]) % M;
        }

        auto [nh, nc] = next_state(hi, cur, S[i]);
        hi = nh;
        cur = nc;
    }

    cout << rank % M << '\n';
    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