Submission #168559

#	Time	Username	Problem	Language	Result	Execution time	Memory
168559		DavidDamian	Linear Garden (IOI08_linear_garden)	C++11	75 / 100	23 ms	1272 KiB

linear_garden

#include <iostream>
#include<stack>
using namespace std;
///Dynamic Programming
///Determine the position of a given string
int memo[2][5][5][5];
int n,m;
int A[1000005];
//The string cannot exceed 2 between L and P, so we keep variables Max and Min
struct node
{
    int i,Min,Max,act;
};
stack<node> S; //Stack to keep track of the next node we have to add to the answer
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    if(n>100000){
        cout<<0<<'\n';
        return 0;
    }
    for(int i=0;i<n;i++){
        char plant;
        cin>>plant;
        if(plant=='L') A[i]=1;
        else A[i]=2;
    }
    int Min=2,Max=2,act=2;
    for(int i=0;i<n;i++){
        if(A[i]==2){ //If we choose letter P, then we add all the subtree rooted next L to the answer
            node x={i+1,min(Min,act+1),max(Max,act+1),act+1};
            S.push(x);
            Max=max(Max,act-1);
            Min=min(Min,act-1);
            act=act-1;
        }
        else{
            Max=max(Max,act+1);
            Min=min(Min,act+1);
            act=act+1;
        }
    }
    for(int Min=0;Min<3;Min++){
        for(int Max=2;Max<5;Max++){
            for(int act=0;act<5;act++){
                if(act>Max || act<Min) continue;
                if(Max-Min>2) memo[(n)%2][Min][Max][act]=0;
                else memo[(n)%2][Min][Max][act]=1;
            }
        }
    }
    int position=0;
    if(S.size() && S.top().i==n){
        node x=S.top();S.pop();
        position+=memo[(x.i)%2][x.Min][x.Max][x.act];
        position%=m;
    }
    for(int i=n-1;i>=0;i--){
        for(int Min=0;Min<3;Min++){
            for(int Max=2;Max<5;Max++){
                for(int act=0;act<5;act++){
                    if(act>Max || act<Min) continue;
                    int a=0,b=0;
                    node L={(i+1)%2,min(Min,act+1),max(Max,act+1),act+1};
                    if(L.Max-L.Min<=2 && L.Min>=0 && L.Max<=4 && L.act<=4);
                        a=memo[L.i][L.Min][L.Max][L.act];
                    node R={(i+1)%2,min(Min,act-1),max(Max,act-1),act-1};
                    if(R.Max-R.Min<=2 && R.Min>=0 && R.Max<=4 && R.act<=4);
                        b=memo[R.i][R.Min][R.Max][R.act];
                    memo[i%2][Min][Max][act]=(a+b)%m;
                }
            }
        }
        if(S.size() && S.top().i==i){
            node x=S.top();S.pop();
            position+=memo[(x.i)%2][x.Min][x.Max][x.act];
            position%=m;
        }
    }
    position=position+1; //We add one (The given string)
    position%=m;
    cout<<position<<'\n';
    return 0;
}

Compilation message (stderr)

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:66:21: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
                     if(L.Max-L.Min<=2 && L.Min>=0 && L.Max<=4 && L.act<=4);
                     ^~
linear_garden.cpp:67:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
                         a=memo[L.i][L.Min][L.Max][L.act];
                         ^
linear_garden.cpp:69:21: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
                     if(R.Max-R.Min<=2 && R.Min>=0 && R.Max<=4 && R.act<=4);
                     ^~
linear_garden.cpp:70:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
                         b=memo[R.i][R.Min][R.Max][R.act];
                         ^

• 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: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5
• Subtask 22: 0 / 5
• Subtask 23: 0 / 5