Submission #1309391

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309391		khang2010	Linear Garden (IOI08_linear_garden)	C++20	40 / 100	13 ms	2308 KiB

linear_garden

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

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() {
    int N;
    ll M;
    string S;
    cin >> N >> M >> S;

    static ll ways[205][3][3];
    memset(ways, 0, sizeof(ways));

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

    // DP
    for (int i = N - 1; i >= 0; i--) {
        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 = (v + ways[i + 1][nh][nc]) % M;
                }
                ways[i][h][c] = v;
            }
        }
    }

    // rank
    ll rank = 1;  // numbering starts from 1
    int hi = 0, cur = 0;

    for (int i = 0; i < N; i++) {
        if (S[i] == 'P') {
            auto [nh, nc] = next_state(hi, cur, 'L');
            if (nh != -1)
                rank = (rank + ways[i + 1][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: 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