Submission #1229912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229912		Uniq0rn	Linear Garden (IOI08_linear_garden)	C++20	100 / 100	11 ms	5456 KiB

linear_garden

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

#define ll long long
#define all(x) begin(x),end(x)
#define sz(x) (int)x.size()
#define ul unsigned long long

int gcd(int a,int b) {return b == 0 ? a:gcd(b,a%b);}

const int N = 1e6 + 10;

int pw[N];

int main() {
    cin.tie(0)->sync_with_stdio(false);
    int n,m;cin >> n >> m;
    string s;cin >> s;
    pw[0] = 1;
    for(int i=1;i<N;i++){
        pw[i] = pw[i - 1] * 2 % m;
    }

    int ans = 0;
    int diff = 0,mx = 0,mn = 0;
    for(int i=0;i<n;i++){
        if(s[i] == 'P'){
            int k = n - i - 1;

            int ndiff = diff + 1;
            int nmx = max(mx,ndiff);
            int nmn = min(mn,ndiff);

            ll res = 0;
            if(nmx - nmn <= 2){
                if(nmx - nmn == 2){
                    if(nmx == ndiff || nmn == ndiff){
                        res = pw[k / 2];
                    }
                    else{
                        res = pw[(k + 1) / 2];
                    }
                }
                else{
                    res = (pw[k / 2] + pw[(k + 1) / 2] - 1 + m) % m;
                }
            }

            ans = (ans + res) % m;
            
        }

        if(s[i] == 'L'){
            diff++;
        }
        else diff--;
        mn = min(mn,diff);
        mx = max(mx,diff);
    }
    
    cout << (ans + 1) % m;
    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