Submission #559848

#	Time	Username	Problem	Language	Result	Execution time	Memory
559848		_Body	Linear Garden (IOI08_linear_garden)	C++17	100 / 100	266 ms	2416 KiB

linear_garden

#include<bits/stdc++.h>
#define int long long
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r){
    uniform_int_distribution<int> uid(l, r);
    return uid(rng);
}
string s;
int N,M;
int dp[(int)(1e6+4)][2][5][5][5];
int DP() 
{

for(int i=N;i>=0;i--)
{
    for(int tight=0;tight<2;tight++)
    {
        for(int mn=0;mn<=2;mn++)
        {
            for(int mx=2;mx<=4;mx++)
            {
                if(mx-mn>2)
                    continue;
                for(int where=mn;where<=mx;where++)
                {
                    if(tight)
                    {
                        int &ret=dp[i&1][1][mn][mx][where];
                        ret=0;
                     if(i==N){
                        ret=1;
                        continue;
                    }
                        for(int d=0;d<=s[i]-'0';d++)
                        {
                            if(d==s[i]-'0')
                            {
                                if(d==0&&where-1>=0)
                                ret+=dp[(i+1)&1][1][min(mn,where-1)][mx][where-1];
                            else if(d==1&&where+1<5) ret+=dp[(i+1)&1][1][mn][max(mx,where+1)][where+1];
                            }
                            else {
                                 if(d==0&&where-1>=0)
                                ret+=dp[(i+1)&1][0][min(mn,where-1)][mx][where-1];
                            else if(d==1&&where+1<5) ret+=dp[(i+1)&1][0][mn][max(mx,where+1)][where+1];
                            }
                            ret=ret%M;
                        }
                    }
                    else {
                         int &ret=dp[i&1][0][mn][mx][where];
                         ret=0;
                           if(i==N){
                        ret=1;
                        continue;
                    }
                        for(int d=0;d<=1;d++)
                        {
                            if(d==s[i]-'0')
                            {
                                if(d==0&&where-1>=0)
                                ret+=dp[(i+1)&1][0][min(mn,where-1)][mx][where-1];
                            else if(d==1&&where+1<5) ret+=dp[(i+1)&1][0][mn][max(mx,where+1)][where+1];
                            }
                            else {
                                 if(d==0&&where-1>=0)
                                ret+=dp[(i+1)&1][0][min(mn,where-1)][mx][where-1];
                            else if(d==1&&where+1<5) 
                                ret+=dp[(i+1)&1][0][mn][max(mx,where+1)][where+1];
                            }
                            ret=ret%M;
                        }
                    }
                }
            }
        }
    }
}
return dp[0][1][2][2][2];
}
int32_t main()
{
ios_base::sync_with_stdio(false);
    cin.tie(NULL);
// freopen("team.in","r",stdin);
// freopen("team.out","w",stdout);
int tt=1;
// cin>>tt;

int T=1;
while(tt--)
{
cin>>N>>M;
cin>>s;
for(int i=0;i<N;i++)
{
    if(s[i]=='L')
        s[i]='0';
    else s[i]='1';
}
cout<<DP()<<"\n";
//cout<<s<<"\n";




}
}

/*stolen stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?)
    * do smth instead of nothing and stay organized
    * WRITE STUFF DOWN
    * DON'T GET STUCK ON ONE APPROACH
*/

Compilation message (stderr)

linear_garden.cpp: In function 'int32_t main()':
linear_garden.cpp:93:5: warning: unused variable 'T' [-Wunused-variable]
   93 | int T=1;
      |     ^

• 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