Submission #1178974

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178974		vicvic	Linear Garden (IOI08_linear_garden)	C++20	100 / 100	14 ms	9188 KiB

linear_garden

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstdint>
#define int long long
using namespace std;
const int NMAX=1e6;
int n, mod, e[NMAX+5];
string s;
int ans=1;
int32_t main ()
{
    ios :: sync_with_stdio (0);
    cin.tie (nullptr);
    cin >> n >> mod >> s;
    e[0]=1;
    for (int i=1;i<=n;i++)
    {
        e[i]=2*(e[i-1])%mod;
    }
    int mx=0, mn=0, crt=0;
    for (int i=0;i<n;i++)
    {
        int len=n-i-1;
        if (s[i]=='P')
        {
            int temp_mx=max (mx, crt+1);
            if (temp_mx-mn==2)
            {
                if (crt+1==temp_mx-1)
                {
                    ans=ans+e[(len+1)/2];
                    ans%=mod;
                }
                else
                {
                    ans=ans+e[len/2];
                    ans%=mod;
                }
            }
            else if (temp_mx-mn==1)
            {
                ans=ans+e[(len+1)/2]+e[(len)/2]-1;
                ans%=mod;
            }
            mn=min (mn, --crt);
        }
        else
            mx=max (mx, ++crt);
    }
    cout << ans;
    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