Submission #230007

#	Time	Username	Problem	Language	Result	Execution time	Memory
230007		CaroLinda	Linear Garden (IOI08_linear_garden)	C++14	63 / 100	133 ms	65016 KiB

linear_garden

#include <bits/stdc++.h>

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#define mkt make_tuple
#define debug printf
#define all(x) x.begin(),x.end()
#define lp(i,a,b) for(int i = a ; i< b ; i++)
#define ss second
#define ff first
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define mk make_pair

const int MAXN = 1e6+1 ;

using namespace std ;

int N  , M ;
int dp[MAXN][4][4] ;
char str[MAXN] ;

int main()
{

    scanf("%d %d %s", &N , &M , str ) ;

    for(int i = 0 ; i < 5 ; i++ )
        for(int j = 0 ; j < 5 ; j++ ) dp[0][i][j] = 1LL ;

    for(int tam = 1 ; tam <= N ; tam ++ )
        for(int l = 0 ; l < 5 ; l++ )
            for(int p = 0 ; p < 5 ; p++ )
            {
                if( l+1 <= 4 && p-1 >= 0 )
                {
                    if( l+1 == 4 ) dp[tam][l][p] = ( tam == 1 ) ? 1LL : dp[tam-2][3][ max(3,p) ] ;
                    else dp[tam][l][p] = dp[tam-1][max(l+1,3)][p-1] ;
                }
                if( p+1 <= 4 && l-1 >= 0 )
                {
                    if( p+1 == 4 ) ( dp[tam][l][p] += (tam==1) ? 1LL : dp[tam-2][ max(l,3) ][ 3 ] ) %= M ;
                    else ( dp[tam][l][p] += dp[tam-1][l-1][ max(3,p+1) ] ) %= M ;
                }
            }

    int cnt = 0 , l = 2 , p = 2;

    for(int i = 0 ; i < N ; i++ )
    {

        int lef = N - i - 1 ;
        if( str[i] == 'P'  )
        {
            if( l+1 == 4 )
            {
                if( lef == 1 ) cnt = (cnt+1) % M ;
                else (cnt += dp[lef-1][3][ max(3,p) ]) %= M ;
            }
            else (cnt += dp[lef][max(l+1,3)][p-1] ) %= M ;
        }

        if(str[i] == 'L')
        {
            if( l+1 == 4 ) l = p = 3 , i++ ;
            else l = max(l+1, 3) , p-- ;
        }
        else
        {
            if( p+1  == 4) l = p = 3 , i++ ;
            else p = max(p+1, 3) , l-- ;
        }
    }

    printf("%d\n" , (cnt+1)%M ) ;

}

Compilation message (stderr)

linear_garden.cpp:4:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
linear_garden.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
linear_garden.cpp: In function 'int main()':
linear_garden.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %s", &N , &M , str ) ;
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
linear_garden.cpp:32:51: warning: iteration 4 invokes undefined behavior [-Waggressive-loop-optimizations]
         for(int j = 0 ; j < 5 ; j++ ) dp[0][i][j] = 1LL ;
                                       ~~~~~~~~~~~~^~~~~
linear_garden.cpp:32:27: note: within this loop
         for(int j = 0 ; j < 5 ; j++ ) dp[0][i][j] = 1LL ;
                         ~~^~~
linear_garden.cpp:32:51: warning: iteration 4 invokes undefined behavior [-Waggressive-loop-optimizations]
         for(int j = 0 ; j < 5 ; j++ ) dp[0][i][j] = 1LL ;
                                       ~~~~~~~~~~~~^~~~~
linear_garden.cpp:31:23: note: within this loop
     for(int i = 0 ; i < 5 ; i++ )
                     ~~^~~
linear_garden.cpp:32:49: warning: array subscript is above array bounds [-Warray-bounds]
         for(int j = 0 ; j < 5 ; j++ ) dp[0][i][j] = 1LL ;
                                       ~~~~~~~~~~^

• Subtask 1: 2 / 2
• Subtask 2: 2 / 2
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 0 / 4
• Subtask 6: 4 / 4
• Subtask 7: 4 / 4
• Subtask 8: 0 / 4
• Subtask 9: 4 / 4
• Subtask 10: 4 / 4
• Subtask 11: 0 / 4
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 0 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5
• Subtask 21: 5 / 5
• Subtask 22: 0 / 5
• Subtask 23: 0 / 5