제출 #312433

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
312433		mohamedsobhi777	Linear Garden (IOI08_linear_garden)	C++14	100 / 100	630 ms	14108 KiB

linear_garden

#include<bits/stdc++.h>


#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")

#define I inline void 
#define S struct 
#define vi vector<int> 
#define vii vector<pair<int,int>>
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std ; 
using ll = long long ; 
using ld = long double ; 

const int N = 1e6 + 7 ; 
const ll inf = 2e18 ; 

// How interesting!

int n, mod,ans;

int dp[2][5][5][5] ; 
int pref_cur[N], prefA[N], prefB[N] ; 

string s ;

inline int add(int x, int y){return x + y >= mod ? x + y - mod : x + y ;}

int get(int i , int j , int k){
        if(abs(j - k) > 2)return 0 ; 
        return dp[1][i][j][k] ; 
}

int solve(int i , int cur ,int A , int B){
        if(abs(A - B) > 2)return dp[0][cur][A][B] = 0 ; 
        if(i == n)return dp[0][cur][A][B] = 1 ; 
        int ret = 0 ; 
        ret = add(ret , get(cur + 1, A , max(B , cur + 1) ) ) ; 
        ret = add(ret , get(cur - 1, min(A , cur - 1) , B ) ) ;

        return dp[0][cur][A][B] = ret; 
}

void shift(){
        for(int i = 0 ;i < 5 ;++ i){
                for(int j = 0 ;j < 5 ; ++ j){
                        for(int k = 0 ; k < 5 ;++ k){
                                dp[1][i][j][k] = dp[0][i][j][k] ;  
                                dp[0][i][j][k] = 0 ; 
                        }
                }
        }
}

int main(){
        ios_base::sync_with_stdio(0) ;
        cin.tie(0) ; 
        //freopen("in.in" , "r" , stdin) ; 
        memset(dp , -1 , sizeof dp) ; 
        cin >> n >> mod >> s ; 

        for(int i = 0 ;i < n; ++ i){
                pref_cur[i] = (i ? pref_cur[i-1] : 0) + (s[i] == 'L' ? 1 : -1)  ; 
                prefA[i] = min( (i ? prefA[i-1] : (int)2) , pref_cur[i] + 2 ) ;
                prefB[i] = max( (i ? prefB[i-1] : 2) , pref_cur[i] + 2 ) ;  
        }

        for(int j = 0 ;j < 5; ++ j)
                for(int k = 0 ; k < 5 ; ++ k)
                        for(int r = 0 ; r < 5 ;++ r)
                                solve(n, j , k , r) ;
        shift() ;
        for(int i = n - 1; ~i; -- i){
                if(s[i] == 'P'){ // 0 
                        int a0 = (i?pref_cur[i-1]+3:3);
                        int A0 = (i?prefA[i-1]:2);
                        int B0 = (i?max( pref_cur[i-1] + 1 + 2 ,prefB[i-1]):3) ;
                        ans = add(ans, get( a0 , A0 , B0) ) ; 
                }
                
                for(int j = 0 ;j < 5 ; ++ j)
                        for(int k = 0 ; k < 5 ; ++ k)
                                for(int r = 0 ; r < 5 ;++ r){
                                        solve(0, j , k , r) ;
                                }
                shift() ; 

        }

        cout<< ++ ans % mod ; 
        return 0 ; 
}

/*
        - bounds sir (segtree = 4N, eulerTour = 2N, ...)
        - a variable defined twice?
        - will overflow?
        - is it a good complexity?
        - don't mess up indices (0-indexed vs 1-indexed)
        - reset everything between testcases. 
*/

• 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