제출 #262948

#제출 시각아이디문제언어결과실행 시간메모리
262948amiratouLinear Garden (IOI08_linear_garden)C++14
0 / 100
53 ms65540 KiB
#pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; #define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) #define rando mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) #define fi first #define se second #define debug(x) cerr << " - " << #x << ": " << x << endl; #define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl; #define debugii(x) cerr << " - " << #x << ": " << x.fi<<","<<x.se << endl; #define sep() cerr << "--------------------" << endl; #define all(x) (x).begin(),(x).end() #define sz(x) (ll)x.size() #define ld long double #define ll long long //#define int ll #define ii pair<int,int> #define v vector<int> #define vii vector<ii> #define vv vector<vector<int> > #define mp make_pair #define INF 1000000000 #define pb push_back #define EPS 1e-9 const int MOD = 1000000007; // 998244353 const int MX = 1000001; string S; int n,m,dp[MX][16][5]; int solve(int idx,int mask,int cnt){ if(idx==n)return 1; if(dp[idx][mask][cnt]!=-1) return dp[idx][mask][cnt]; int h=cnt-2,ans=0; if((h+1) <=2){ h++; if((h==2) && !(((mask>>2)&1)|((mask>>3)&1)))ans=(ans+solve(idx+1,mask|(1<<0),h+2))%m; if((h==1) && !((mask>>3)&1))ans=(ans+solve(idx+1,mask|(1<<1),h+2))%m; if(h==0)ans=(ans+solve(idx+1,mask,h+2))%m; if((h==-1) && !((mask>>0)&1))ans=(ans+solve(idx+1,mask|(1<<2),h+2))%m; if((h==-2) && !(((mask>>0)&1)|((mask>>1)&1)))ans=(ans+solve(idx+1,mask|(1<<3),h+2))%m; h--; } if((h-1) >=-2){ h--; if((h==2) && !(((mask>>2)&1)|((mask>>3)&1)))ans=(ans+solve(idx+1,mask|(1<<0),h+2))%m; if((h==1) && !((mask>>3)&1))ans=(ans+solve(idx+1,mask|(1<<1),h+2))%m; if(h==0)ans=(ans+solve(idx+1,mask,h+2))%m; if((h==-1) && !((mask>>0)&1))ans=(ans+solve(idx+1,mask|(1<<2),h+2))%m; if((h==-2) && !(((mask>>0)&1)|((mask>>1)&1)))ans=(ans+solve(idx+1,mask|(1<<3),h+2))%m; h++; } return dp[idx][mask][cnt]=ans; } int32_t main(){ boost; //freopen(".in","r",stdin); memset(dp,-1,sizeof dp); cin>>n>>m>>S; int ans=0,cnt=0,mask=0; for (int i = 0; i < n; ++i){ if((S[i]=='P') && ((cnt+1)<=2)){ cnt++; if((cnt==2) && !(((mask>>2)&1)|((mask>>3)&1)))ans=(ans+solve(i+1,mask|(1<<0),cnt+2))%m; if((cnt==1) && !((mask>>3)&1))ans=(ans+solve(i+1,mask|(1<<1),cnt+2))%m; if(cnt==0)ans=(ans+solve(i+1,mask,cnt+2))%m; if((cnt==-1) && !((mask>>0)&1))ans=(ans+solve(i+1,mask|(1<<2),cnt+2))%m; if((cnt==-2) && !(((mask>>0)&1)|((mask>>1)&1)))ans=(ans+solve(i+1,mask|(1<<3),cnt+2))%m; cnt--; } cnt+=((S[i]=='P')?-1:1); if(cnt==-1)mask|=(1<<2); else if(cnt==1)mask|=(1<<1); else if(cnt==2)mask|=(1<<0); else if(cnt==-2)mask|=(1<<3); } cout<<(ans+1)%m<<"\n"; return 0; } //do smth instead of nothing and stay organized //long long //array bounds //special cases //binary search
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...