Submission #754086

#	Time	Username	Problem	Language	Result	Execution time	Memory
754086		AndresRPerez	Linear Garden (IOI08_linear_garden)	C++17	0 / 100	45 ms	65536 KiB

linear_garden

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6+1;
const int B = 4;
const int M = 1<<B;

int n, m;
string s;

int mem [N][M];

bool checkBit( int mask , int b ){
    return ( mask & (1<<b) ) > 0;
}

int addToMask( int mask , int newBit, bool eraseOld = true ){
    mask <<= 1;
    if( eraseOld and checkBit(mask, B) ) mask ^= (1<<B);
    if( newBit ) mask |= 1;
    return mask;
}

bool checkMask( int mask, int sz = B+1 ){
    if( sz <= 2 ) return true;
    for( int i = 0 ; i+3 < sz ; i ++ ){
        int cnt = 0;
        for( int j = i ; j < sz ; j ++ ){
            if( checkBit( mask, j ) ) cnt ++;
            else cnt --;
            if( abs(cnt) > 2 ) return false;
        }
    }
    return true;
}

int dp( int left, int mask ){
    //cout << "IN " << left << " " << mask << " :: sz " << min( n - left + 1, B ) << endl ;
    if( left == 0 ) return 1;
    int &ret = mem[left][mask];
    if( ret != -1 ) return ret;
    
    ret = 0;
    int sz = min( n - left + 1, B+1 );
    
    for( int nxt = 0 ; nxt <= 1 ; nxt ++ ){
        int newMask = addToMask( mask, nxt, false );
        //cout << "   TRY " << left-1 << " " << newMask << " from " << left << " " << mask << endl ;
        if( checkMask( newMask , sz ) ){
            ret += dp( left-1, addToMask( mask, nxt ) );
            ret %= m;
        }
    }
    return ret;
}

int main()
{   
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    memset(mem, -1, sizeof(mem));
    cin >> n >> m >> s ;
    
    int mask = 0, left = n;
    int ans = 0;
    for( int i = 0 ; i < n ; i ++ ){
        if( s[i] == 'P' ){
            ans += dp( n-i-1, addToMask( mask, 0 ) );
            ans %= m;
        }
        if( s[i] == 'L' ) mask = addToMask( mask, 0 );
        else mask = addToMask( mask, 1 );
    }
    cout << ans << endl ;

    return 0;
}

Compilation message (stderr)

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:74:19: warning: unused variable 'left' [-Wunused-variable]
   74 |     int mask = 0, left = n;
      |                   ^~~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 2
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 4
• Subtask 7: 0 / 4
• Subtask 8: 0 / 4
• Subtask 9: 0 / 4
• Subtask 10: 0 / 4
• Subtask 11: 0 / 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