Submission #1284949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284949		tripleabattery	Linear Garden (IOI08_linear_garden)	C++20	100 / 100	237 ms	9368 KiB

linear_garden

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using namespace chrono;
typedef long long ll;
typedef pair<ll,ll> pii;

ll exp(ll b, ll e, ll m)
{
    if(!e)return 1;
    ll mew=exp(b,e/2,m)%m;
    if(e%2)return (((mew*mew)%m)*b)%m;
    else return (mew*mew)%m;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    ll n,m; cin>>n>>m;
    string s; cin>>s;
    vector<ll> dp(n+1);
    dp[0]=1;
    for(ll i=1;i<=n;i++)
    {
        dp[i]=(exp(2,((i-1)/2),m))+dp[i-1];
    }
    ll ans=1;
    pii mew={2ll,2};
    for(ll i=1;i<=n;i++)
    {
        ll k=n-i;
        if(s[i-1]=='P')
        {
            pii riz={mew.fi-1,min(2ll,mew.se+1)};
            if(riz==pii{1,2}||riz==pii{2,1})ans=(ans+dp[k])%m;
            if(riz==pii{0,2}||riz==pii{2,0})ans=(ans+exp(2,((k)/2),m))%m;
            if(riz==pii{1,1}||riz==pii{1,1})ans=(ans+exp(2,((k+1)/2),m))%m;
            if(riz==pii{1,0}||riz==pii{0,1})ans=(ans+1)%m;
            mew={min(2ll,mew.fi+1),mew.se-1};
        }
        else mew={mew.fi-1,min(2ll,mew.se+1)};
    }
    cout<<(ans%m)<<"\n";
}

• 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