Submission #525844

#	Time	Username	Problem	Language	Result	Execution time	Memory
525844		Deepesson	Linear Garden (IOI08_linear_garden)	C++17	85 / 100	1572 ms	3196 KiB

linear_garden

#include <bits/stdc++.h>

int N,M;
#define MAX 1100000
int tab[2][33][5][2];
int base=2;
std::string s;
int main()
{
    std::cin>>N>>M>>s;
    {
        for(int j=0;j!=33;++j){
            for(int k=-2;k!=3;++k){
                for(int v=0;v!=2;++v){
                    for(int u=0;u!=5;++u){
                        if(j&(1<<u)){
                            int _ = u-2;
                            int __ = k-_;
                            if(__>2||__<-2) goto prox;
                        }
                    }{
                    tab[N%2][j][k+2][v]=1;}
                    prox:{}
                }
            }
        }
    }
    for(int i=N-1;i!=-1;--i){
        for(int j=0;j!=33;++j){
            for(int k=-2;k!=3;++k){
                for(int v=0;v!=2;++v){
                    int pente=j;
                    int pos=i;
                    int atual,soma;
                    atual=soma=k;
                    int desceu=v;
                    for(int u=0;u!=5;++u){
                        if(j&(1<<u)){
                            int _ = u-2;
                            int __ = k-_;
                            if(__>2||__<-2) {tab[pos%2][pente][soma+2][desceu]=0;goto proxa;}
                        }
                    }
                    if(v){
                        int alpha=0,beta=0;
                        if(atual<2){
                            alpha=tab[(pos+1)%2][pente|(1<<(soma+3))][soma+3][1];
                        }

                        if(atual>-2){
                            beta=tab[(pos+1)%2][pente|(1<<(soma+1))][soma+1][1];
                        }

                        tab[pos%2][pente][soma+2][desceu] = ( alpha + beta ) % M;
                    }else {
                    if(s[pos]=='L'){

                        if(atual>-2){///Aperta L
                            tab[pos%2][pente][soma+2][desceu] = tab[(pos+1)%2][pente|(1<<(soma+1))][soma+1][0];
                        }else tab[pos%2][pente][soma+2][desceu]=0;

                    }else {

                        int alpha=0,beta=0;

                        if(atual<2){///Aperta P
                            alpha=tab[(pos+1)%2][pente|(1<<(soma+3))][soma+3][0];
                        }

                        if(atual>-2){///Aperta L
                            beta=tab[(pos+1)%2][pente|(1<<(soma+1))][soma+1][1];
                        }

                        tab[pos%2][pente][soma+2][desceu] = ( alpha + beta ) % M;

                    }
                }
                    ///Invalido
                    proxa:{}
                }
            }
        }
    }
    std::cout<<tab[0][(1<<2)][2][0]<<"\n";
}

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