Submission #1309390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309390		khang2010	Linear Garden (IOI08_linear_garden)	C++20	0 / 100	143 ms	131072 KiB

linear_garden

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

/*
 diff = maximum position reached so far
 rel  = current position (0 <= rel <= diff)
 diff is capped at 2
*/

pair<int,int> get_next(int diff, int rel, char ch) {
    int new_diff = diff;
    int new_rel = rel;

    if (ch == 'L') {
        new_rel = rel + 1;
        new_diff = max(diff, new_rel);
    } else { // 'P'
        if (rel > 0) {
            new_rel = rel - 1;
        } else {
            // shift origin to the right
            new_rel = 0;
            new_diff = diff + 1;
        }
    }

    if (new_diff > 2) return {-1, -1};
    return {new_diff, new_rel};
}

int main() {
    int N;
    ll M;
    string S;

    cin >> N;
    cin >> M;
    cin >> S;

    // ways[pos][diff][rel]
    vector<vector<vector<ll>>> ways(
        N + 1, vector<vector<ll>>(3, vector<ll>(3, 0))
    );

    // Base case: any valid state at position N
    for (int d = 0; d <= 2; d++) {
        for (int r = 0; r <= d; r++) {
            ways[N][d][r] = 1;
        }
    }

    // DP computation
    for (int pos = N - 1; pos >= 0; pos--) {
        for (int d = 0; d <= 2; d++) {
            for (int r = 0; r <= d; r++) {
                ll val = 0;

                auto [d1, r1] = get_next(d, r, 'L');
                if (d1 != -1)
                    val = (val + ways[pos + 1][d1][r1]) % M;

                auto [d2, r2] = get_next(d, r, 'P');
                if (d2 != -1)
                    val = (val + ways[pos + 1][d2][r2]) % M;

                ways[pos][d][r] = val;
            }
        }
    }

    // Lexicographic rank
    ll rank = 0;
    int cur_diff = 0, cur_rel = 0;

    for (int pos = 0; pos < N; pos++) {
        if (S[pos] == 'P') {
            // try smaller letter 'L'
            auto [d, r] = get_next(cur_diff, cur_rel, 'L');
            if (d != -1)
                rank = (rank + ways[pos + 1][d][r]) % M;
        }

        auto [nd, nr] = get_next(cur_diff, cur_rel, S[pos]);
        cur_diff = nd;
        cur_rel = nr;
    }

    cout << rank << "\n";
    return 0;
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 2
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 4
• Subtask 7: 0 / 4
• Subtask 8: 0 / 4
• Subtask 9: 0 / 4
• Subtask 10: 0 / 4
• Subtask 11: 0 / 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