Submission #125328

#	Time	Username	Problem	Language	Result	Execution time	Memory
125328		Nodir_Bobiev	Paint By Numbers (IOI16_paint)	C++14	100 / 100	933 ms	186496 KiB

paint

# include <iostream>
# include <vector>

using namespace std;

const int N = 2e5 + 100;
string S;
vector < int > C;
int n, k;
int W[N][111], B[N][111], pfW[N], pfB[N];

int get( int l, int r, int st )
{
    if( st == 0 ){
        if( l )return pfW[r] - pfW[l-1];
        else return pfW[r];
    }else {
        if( l ) return pfB[r] - pfB[l-1];
        else return pfB[r];
    }
}

bool rec( int i, int j, int st )
{
    if( i == n ){ return (j==k); }
    if( st == 0 && W[i][j] != -1 )
        return W[i][j];
    if( st == 1 && B[i][j] != -1 )
        return B[i][j];


    if( st == 0 ){
        if( S[i] != 'X' )
            return W[i][j] = ( rec( i+1, j, 0 ) | rec( i+1, j, 1 ) );
        return W[i][j] = 0;
    }


    else if( st == 1 ){
        if ( j < k && i+C[j] <= n && get( i, i+C[j]-1, 0 ) == 0 )
            return B[i][j] = ( rec( i+C[j], j+1, 0 ) );
        return B[i][j] = 0;
    }
}

string solve_puzzle( string s, vector < int > c )
{
    n = s.size(); k = c.size();
    S = s; C = c;

    for( int i = 0; i <= n; i ++ ){
        for( int j = 0; j <= k; j ++ ){
            W[i][j] = -1;
            B[i][j] = -1;
        }
    }
    for( int i = 0; i < n; i ++ ){
        if( i ){
            pfW[i] = pfW[i - 1];
            pfB[i] = pfB[i - 1];
        }if( S[i] == 'X' ){
            pfB[i] ++;
        }if( S[i] == '_' ){
            pfW[i] ++;
        }
    }
    rec( 0,0,0 );
    rec( 0,0,1 );
    int black_able = -1, white_able = 0;
    string answer;
    for( int i = 0; i < n; i ++ ){
        white_able = 0;
        for( int j = 0; j <= k; j ++ ){
            if( B[i][j] == 1) black_able = max( black_able, i+C[j]-1);
            if( W[i][j] == 1) white_able = true;
        }
        if( black_able >= i && white_able ){
            answer += '?';
        }else if( black_able >= i ){
            answer += 'X';
        }else if( white_able ){
            answer += '_';
        }
    }
    /*
    cout << "Black :" << endl;
    for( int i = 0; i <= n; i ++ ){
        for( int j = 0; j <= k; j ++ ){
            cout << B[i][j] << ' ';
        }cout << endl;
    }
    cout << "White :" << endl;
    for( int i = 0; i <= n; i ++ ){
        for( int j = 0; j <= k; j ++ ){
            cout << W[i][j] << ' ';
        }
        cout << endl;
    }
    */
    return answer;
}
/*
int main()
{
    string ans;
    ans = solve_puzzle( ".X........", { 3 } );
    cout << ans;
    return 0;
}
*/

Compilation message (stderr)

paint.cpp: In function 'bool rec(int, int, int)':
paint.cpp:34:28: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
             return W[i][j] = ( rec( i+1, j, 0 ) | rec( i+1, j, 1 ) );
                    ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
paint.cpp:35:24: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
         return W[i][j] = 0;
                ~~~~~~~~^~~
paint.cpp:41:28: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
             return B[i][j] = ( rec( i+C[j], j+1, 0 ) );
                    ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
paint.cpp:42:24: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
         return B[i][j] = 0;
                ~~~~~~~~^~~
paint.cpp:44:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 21 / 21
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10