oj.uz

Submission #554945

# Submission time Handle Problem Language Result Execution time Memory
554945 2022-04-29T16:51:43 Z alextodoran Linear Garden (IOI08_linear_garden) C++17
100 / 100
 18 ms 10304 KB 
/**
 ____ ____ ____ ____ ____
||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

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #7
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #8
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #9
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #10
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #11
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3392 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4328 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5352 KB Output is correct

Subtask #22
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6556 KB Output is correct

Subtask #23
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 10304 KB Output is correct
2 Correct 18 ms 10216 KB Output is correct
3 Correct 13 ms 10224 KB Output is correct