| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 266878 | youssefbou62 | Linear Garden (IOI08_linear_garden) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;
#define mp make_pair
#define fi first
#define se second
#define all(v) v.begin(),v.end()
#define allarr(a) a , a + n
#define ll long long
#define pb push_back
#define fastio ios_base::sync_with_stdio(false) ; cin.tie(NULL); cout.tie(NULL)
#define sz(x) (int)x.size()
typedef pair<int, int> pi;
typedef pair<ll,ll> pll ;
typedef pair<int,pi> trp ;
typedef vector<pi> vpi;
typedef priority_queue< pi, vector <pi> , greater<pi> > spq;
const int MAXN = 1e6+5 ;
int dp[MAXN][2][7][7][7];
int N ;
int M ;
string s;
void add(int& x ,int y ){
x = ( x % M + y % M ) % M ;
}
void solve (){
vector<int> S ;
for(int i = 0 ; i < N ; i++ )S.pb(s[i]=='P');
dp[0][0][2][2][2] = 1 ;
for(int i = 0 ; i < N ; i++ ){
for(int pref = -2 ; pref <= 2 ; pref++ )
for(int hpref = -2 ; hpref <= 2 ; hpref++ )
for(int lpref = -2 ; lpref <= 2 ; lpref++ ){
for(int choice : {0,1}){
int nxt_pref = pref ;
if( choice )nxt_pref++;else nxt_pref--;
int x = min(nxt_pref,lpref) ;
int y= max(nxt_pref,hpref);
if( abs(hpref-lpref) > 2 || nxt_pref==3 || nxt_pref==-3||x == -3 || y == 3 || y == -3 || x == 3 )continue ;
if(choice < S[i])
add(dp[i+1][1][3+nxt_pref][3+x][3+y],dp[i][0][pref+3][lpref+3][hpref+3]);
if(choice == S[i])
add(dp[i+1][0][3+nxt_pref][3+x][3+y],dp[i][0][pref+3][lpref+2][hpref+3]);
add(dp[i+1][1][3+nxt_pref][3+x][3+y],dp[i][1][pref+3][lpref+3][hpref+3]);
}
// if(dp[i][1][pref][lpref][hpref])
// cout << i << " " << pref << " " <<lpref << " " <<hpref<<endl;
}
}
int ans = 1 ;
for(int pref = -2 ; pref <= 2 ; pref++ )
for(int hpref = -2 ; hpref <= 2 ; hpref++ )
for(int lpref = -2 ; lpref <= 2 ; lpref++)
if( abs(hpref-lpref) <= 2 )
add(ans,dp[N][1][pref+3][lpref+3][hpref+3]);
cout << ans << endl;
}
int main(){
// ifstream cin("in.in");
cin >> N >> M >> s ;
solve() ;
}