Submission #1370119

#	Time	Username	Problem	Language	Result	Execution time	Memory
1370119		magentor	Linear Garden (IOI08_linear_garden)	C++20	100 / 100	53 ms	2416 KiB

linear_garden

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
#define rep2(i, m ,n) for (int i = (m); i < (long long)(n); i++)
#define REP(i, n) for (long long i = 1; i < (long long)(n); i++)
typedef long long ll;
#define l(n) n.begin(),n.end()
#define YesNo(Q) Q==1?cout<<"Yes":cout<<"No"
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
int main(){
  ll n,m;cin>>n>>m;
  string s;cin>>s;
  //"L,P"
  ll ans = 0;
  int cnt = 0;
  int mn = 0;
  int mx = 0;
  rep(i,s.size()){
    int mn1 = min(mn,cnt-1);
    int mx1 = max(mx,cnt-1);
    int ncnt = cnt-1;
    if(-2<=mn1 && s[i]=='P'){
      
      for(int j = -1;1>=j;j++){
        if(mn1>=j-1&&j+1>=mx1){
          
          if(j==ncnt){
            //(s.size()-i)/2
            ans += modpow(2LL,(s.size()-i)/2,m);
            ans %= m; 
          }
          else{
            ans += modpow(2LL,(s.size()-i-1)/2,m);
            ans %= m; 
          }
        }
      }
      //cout<<mn1<<" "<<mx1<<endl;
      for(int j = 0;j<=1;j++){
        if(mn1>=j-1&&j>=mx1){
          ans--;
          ans %= m; 
        }
      }
    }
    
    if(s[i]=='P'){cnt++;mx = max(mx,cnt);}
    else{cnt--;mn=min(mn,cnt);}
  }
  ans = (ans+1)%m;
  cout << ans << endl;
}

• 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