제출 #219835

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

linear_garden

#include <bits/stdc++.h> 
 
using namespace std ; 
const int N = 5e5 + 7 ; 
long long n , mod , ans ; 
string s ; 
 
int mv2[2] = {0 , 1} , mv1[2] = {1 , 0} ; 
 
long long add (long long a , long long b){
    return (a%mod + b%mod + mod) %mod ; 
}
 
int dp[N][3][3][3];
 
void normalize(int &a , int &b , int &A , int &B){
    int mn = min(a , b) ; 
    a-=mn ; 
    b-=mn; 
    A = max( A , a - b ); 
    B = max(B , b - a); 
}
 
long long solve(int i , int ab , int A , int B){
    int a = max(0 , ab-2) ; 
    int b = max(0 , 2-ab) ; 
    if(dp[i][ab][A][B]!=-1)
        return dp[i][ab][A][B] ; 
    if( a + B > 2 || b + A > 2 ) return 0 ; 
    if(i==n){
        return 1 ; 
    }
    long long ret = 0 ; 
    for(int j = 0 ; j< 2 ;j++){
        int na = a + mv1[j] ; 
        int nb = b + mv2[j] ; 
        int tmpA = A; 
        int tmpB = B; 
        int nab = na - nb + 2 ;
        if(nab <0 || nab > 4)continue ; 
        normalize(na , nb , tmpA , tmpB) ; 
        ret= add(ret , solve(i+1 , nab , tmpA , tmpB)) ; 
    }
    return dp[i][ab][A][B] = ret ; 
}

int smart(int i , int l , int d , int b, int val){
    if(i > n)return 0 ; 
    if(i==n){
        return 1 ; 
    }
    int ret = 0 ; 
    
    ret+=smart(i+1 , 1 - l , 0 , d , val* 10 + 1-l) ; 
    if(!b){
        if(d){
            ret+=smart(i+2 , 1-l , 1 , 0 , (val*10 + 1- l)*10  + 1-l  ) ; 
        }else{
            ret+=smart(i+2 , 1-l , 1 ,0 , (val*10 + 1-l) * 10 + 1-l  ) ; 
        }       
    }

    return ret ; 
}
int smart_solve(int i , int l , int d , int b){
    if(!l)b =1  ; 
    int ret = smart(i , l , d , b , 0); 
    return ret ;
}
void brute(int i , string ss){
    
    if(i==n){  
        for(int j = 0 ; j < n;j++){
        int a = 0  , b = 0 ; 
        for(int k = j ; k < n ;k++){
            if(ss[k]=='L'){
                a++ ; 
            }else{
                b++ ; 
            }
            if(abs(a - b) > 2)
                return ; 
        }
    } 
        cout<<ss<<"\n" ; 
        return  ; 
    }
    brute(i+1 , ss+'L')  ;
    brute(i+1 , ss+'P') ; 
}


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

    int a = 0, b =0; 
    int A = 0, B = 0; 
    int ab = 0 ; 

    int l = 1 ; 
    int d = 0 ; 
    int bad = 0 ; 
    int val = 0 ; 
    for(int i = 0 ;i < n;i++){
        if(s[i] == 'L'){
            l = 0 ;     
            val = val*10 + l ; 
        }else{  
            val = val * 10 + 1 ;
            int cant = 0 ; 
            if(i > 1){
                if(s[i-1]=='L' && s[i-2] == 'L'){
                    cant = 1 ; 
                }
            }
            if(cant)continue ; 
            if(i > 1 && l==1)d = 1 ; 
            ans=add (ans , smart_solve(i , l , d ,0 ) );
            l = 1 ; 
        }
        
    }
    cout<<add(ans , 1); 
    return 0 ; 
}

컴파일 시 표준 에러 (stderr) 메시지

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:101:9: warning: unused variable 'a' [-Wunused-variable]
     int a = 0, b =0; 
         ^
linear_garden.cpp:101:16: warning: unused variable 'b' [-Wunused-variable]
     int a = 0, b =0; 
                ^
linear_garden.cpp:102:9: warning: unused variable 'A' [-Wunused-variable]
     int A = 0, B = 0; 
         ^
linear_garden.cpp:102:16: warning: unused variable 'B' [-Wunused-variable]
     int A = 0, B = 0; 
                ^
linear_garden.cpp:103:9: warning: unused variable 'ab' [-Wunused-variable]
     int ab = 0 ; 
         ^~
linear_garden.cpp:107:9: warning: unused variable 'bad' [-Wunused-variable]
     int bad = 0 ; 
         ^~~

• Subtask 1: 2 / 2
• Subtask 2: 0 / 2
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 4
• Subtask 7: 0 / 4
• Subtask 8: 0 / 4
• Subtask 9: 0 / 4
• Subtask 10: 0 / 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