Submission #312413

#	Time	Username	Problem	Language	Result	Execution time	Memory
312413		mohamedsobhi777	Linear Garden (IOI08_linear_garden)	C++14	40 / 100	1587 ms	36116 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 = 2e5 + 7 ; 
const ll inf = 2e18 ; 

// How interesting!

int n, mod;

int dp[N][3][3][3] ; 
string s ;
void normalize(int &a ,  int &b , int &A , int &B){
        int mn = min(a , b) ; 
        a-=mn ; b-=mn ; 
        A = min(A , a - b + 2); 
        B = max(B , a - b + 2);  
} 

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

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

        ret = add(ret , solve(i + 1, cur + 1, A , max(B , cur + 1) ) ) ; 
        ret = add(ret , solve(i + 1, cur - 1, min(A , cur - 1) , B ) ) ;

        return ret; 
}

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 ; 

        int a = 2 , b = 2 , A = 2 , B = 2 ; 
        int ans = 0 ;
        for(int i = 0 ; i < n; ++ i){
                //cout<< a <<" " << b <<" " << A <<" "<< B<<"*\n" ;
                if(s[i] == 'L'){ // 0 
                        a ++ ; 
                        normalize(a , b, A , B) ; 
                }else{ // 1
                        int a0 = a + 1; 
                        int b0 = b; 
                        int A0 = A ; 
                        int B0 = B ;
                        normalize(a0 , b0 , A0 , B0) ; 
                        int cur = a0 - b0 + 2 ; 
                        ans += solve(i + 1, cur , A0 , B0) ; 
                        b ++ ; 
                        normalize(a , b , A , B) ; 
                }
        }

        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: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5
• Subtask 22: 0 / 5
• Subtask 23: 0 / 5