Submission #230012

#	Time	Username	Problem	Language	Result	Execution time	Memory
230012		CaroLinda	Linear Garden (IOI08_linear_garden)	C++14	100 / 100	500 ms	48252 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+3 ;

using namespace std ;

int N  , M ;
int dp[MAXN][12] ;
char str[MAXN] ;
map<pii,int> mp ;

int main()
{
    mp[ mk(-2,2) ] = 0 ;
    mp[ mk(-1,1) ] = 1 ;
    mp[ mk(-1,2) ] = 2 ;
    mp[ mk(0,0) ] = 3 ;
    mp[ mk(0,1) ] = 4 ;
    mp[ mk(0,2) ] = 5 ;
    mp[ mk(1,-1) ] = 6 ;
    mp[ mk(1,0) ] = 7 ;
    mp[ mk(1,1) ] = 8 ;
    mp[ mk(2,-2) ] = 9 ;
    mp[ mk(2,-1) ] = 10 ;
    mp[ mk(2,0) ] = 11 ;

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

    for(int i = 0 ; i < 12 ; i++ ) dp[0][i] = 1 ;

    for(int tam = 1 ; tam <= N ; tam ++ )
        for(auto x : mp )
        {
            pii p = x.ff ;

            pii p1 = mk( max(p.ff + 1,1) , p.ss-1 ) ;
            pii p2 = mk( p.ff-1, max(p.ss+1, 1) ) ;

            if( mp.find(p1) != mp.end() ) dp[tam][x.ss] = dp[tam-1][ mp[p1] ] ;
            if( mp.find(p2) != mp.end() ) ( dp[tam][x.ss] += dp[tam-1][ mp[p2] ] ) %= M ;

        }

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

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

        if( str[i] == 'P' && l < 2 )
            ( cnt += dp[lef][ mp[ mk(max(l+1,1),p-1) ] ] ) %= M ;

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

    }

    printf("%d\n" , cnt ) ;

}

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:42: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 ) ;
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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