oj.uz

Submission #754086

# Submission time Handle Problem Language Result Execution time Memory
754086 2023-06-06T16:28:56 Z AndresRPerez Linear Garden (IOI08_linear_garden) C++17
0 / 100
 45 ms 65536 KB 
/******************************************************************************

                              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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 62932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 62908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 62932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 62848 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 62916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 62816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 62924 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 62932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 62912 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 62876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 62828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 62908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 62980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 63188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 64860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 65076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 37 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 39 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 37 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 37 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #22
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #23
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -