Submission #554945

#	Time	Username	Problem	Language	Result	Execution time	Memory
554945		alextodoran	Linear Garden (IOI08_linear_garden)	C++17	100 / 100	18 ms	10304 KiB

linear_garden

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 1000000;

int N, MOD;
bool A[N_MAX + 2];

int dp[N_MAX + 2][2];
// dp[n][false] = number of good strings of length n,
// with the last double value different from the last value
// dp[n][true] = number of good strings of length n,
// with the last double value equal to the last value

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

    cin >> N >> MOD;
    string s;
    cin >> s;
    for (int i = 1; i <= N; i++) {
        A[i] = (s[i - 1] == 'P');
    }
    for (int n = 2; n <= N; n++) {
        dp[n][true] = dp[n - 1][false] + dp[n - 2][true] + 1;
        dp[n][false] = dp[n - 1][true];
        dp[n][true] %= MOD;
    }

    int answer = 0;
    int last = -1;
    for (int n = 1; n <= N; n++) {
        if (A[n] == 1) {
            int aux = answer;
            if (n > 1 && A[n - 1] == 0) {
                if (last != 0) {
                    answer += dp[N - n + 1][false] + 1;
                }
            } else if (last != -1) {
                answer += dp[N - n + 1][0 == !last] + 1;
            } else {
                answer += (dp[N - n + 1][false] + dp[N - n + 1][true]) + 1;
            }
            answer %= MOD;
        }
        if (n > 1 && A[n - 1] == A[n]) {
            last = A[n];
        }
    }
    answer++; answer %= MOD;
    cout << answer << "\n";

    return 0;
}

Compilation message (stderr)

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:47:17: warning: unused variable 'aux' [-Wunused-variable]
   47 |             int aux = answer;
      |                 ^~~

• 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