Submission #492234

#	Time	Username	Problem	Language	Result	Execution time	Memory
492234		gg123_pe	Linear Garden (IOI08_linear_garden)	C++17	40 / 100	1589 ms	3332 KiB

linear_garden

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

typedef long long ll; 
typedef vector <int> vi; 
#define f(i,a,b) for(int i = a; i < b; i++)
const int N = 1e7 + 5;


ll n, m, ans = 1; 
string s, wi; 

bool is_valid(string s){
    int l = s.size(), c_l[l+1], c_p[l+1];
    f(i,0,l+1) c_l[i] = c_p[i] = 0; 
    f(i,1,l+1){
        c_l[i] = c_l[i-1], c_p[i] = c_p[i-1];
        if(s[i-1] == 'L') c_l[i]++;
        else c_p[i]++;
    }
    f(i,1,l+1){
        f(j,i+2,l+1){
            int CL = c_l[j] - c_l[i-1], CP = c_p[j] - c_p[i-1];
            if(abs(CL-CP) > 2) return 0;
        }
    }
    return 1; 
}

int main(){
    cin >> n >> m >> s; 

    vector <string> c = {"LLL", "LLP", "LPL", "LPP","PLL","PLP", "PPL", "PPP"}; 

    f(i,0,n){
        if(s[i] == 'L'){
            wi.push_back('L');
            continue; 
        }
        // how many are there such that have lenght n-i 
        string aux = wi; 
        aux.push_back('L');
        int cant = 0, ye = n-i-1;
        for(string x: c){
            string ra = aux + x;
            cant += is_valid(ra);
        }
     
        if(cant == 2){ // 1, 2, 2, 4, 4 ,8, 8
            // odd -> 2^(1-1), 2^(2-1)
            // 5 / 2  = 2
            ll add = (1LL<<(ye/2));
            //ans = (ans + add)%m; 
            //cout << aux << " " << cant << " " << ye << " " << add << endl; 
            ans = (ans + add)%m; 
        }
        if(cant == 3){ // 1, 2, 3, 5, 7, 11, 15 
            // +1, +1, +2, +2, +4, +4 
            ll add = (1LL<<((ye+1)/2))-1;
            if(ye%2 == 0){
                add += (1LL<<((ye-1)/2));
            }
            //ans = (ans + add)%m; 
            ans = (ans + add)%m;
            // cout << aux << " " << cant << " " << ye << " " << add << endl; 
        }
        if(cant == 4){ // 2, 2, 4, 4, 
            // + 1 / 2
            ll add = (1LL<<((ye+1)/2));
            //ans = (ans + add)%m; 
            ans = (ans + add)%m;
            // cout << aux << " " << cant << " " << ye << " " << add << endl; 
        }
        if(cant == 5){ // 2, 3, 5, 7, 11, 15
            // +1, +2, +2, +3
            ll add = (1LL<<((ye+1)/2)+1)-1;; 
            if(ye%2 == 1){
                add -= (1LL<<(ye/2));
            }
            //ans = (ans + add)%m; 
            ans = (ans + add)%m; 
            //cout << aux << " " << cant << " " << ye << " " << add << endl; 
        }
        
        wi.push_back('P');
    }
    cout << ans << endl; 
    return 0;
}

Compilation message (stderr)

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:76:38: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   76 |             ll add = (1LL<<((ye+1)/2)+1)-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: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5
• Subtask 22: 0 / 5
• Subtask 23: 0 / 5