Submission #125030

#	Time	Username	Problem	Language	Result	Execution time	Memory
125030		Nodir_Bobiev	Paint By Numbers (IOI16_paint)	C++14	59 / 100	3 ms	396 KiB

paint

# include <iostream>
# include <vector>

using namespace std;

const int N = 2e5 + 100;
bool B[N][111];
bool W[N][111];
bool WW[N][111];
bool BB[N][111];
int pref[N], cnt[N];

bool can( int i, int j )
{
    return ( pref[i+j-1] - pref[i-1] == j );
}

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

    s += '_'; W[n][k] = true;

    for( int i = 0; i < n; i ++ ){
        if( i )
            pref[i] = pref[i - 1];
        if( s[i] != '_' )
            pref[i] ++;
    }

    for( int i = n-1; i >= 0; i -- ){
        for( int j = k; j >= 0; j -- ){
            if( j == k ){
                W[i][j] = (W[i+1][j] & (s[i] != 'X') );
            }
            else if( s[i] == '_' ){
                W[i][j] = W[i+1][j] | B[i+1][j];
            }
            else if( s[i] == 'X' && can( i, c[j] ) ){
                B[i][j] = W[i+c[j]][j+1];
            }
            else{
                W[i][j] = W[i+1][j] | B[i+1][j];
                if( can( i, c[j] ) ){
                    B[i][j] = W[i+c[j]][j+1];
                }
            }
        }
    }
/*
    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;
    }
*/
    BB[0][0] = WW[0][0] = true;
    string ret;
    for( int i = 0; i < n; i ++ ){
        if( i ) cnt[i] += cnt[i - 1];
        bool x = (cnt[i]>0), _ = false;

        for( int j = 0; j <= k; j ++ ){
            if( j<k && BB[i][j] && B[i][j] ){
                x = true;
                WW[i+c[j]][j+1] = true;
                cnt[i]++;
                cnt[i+c[j]]--;
            }
            if( WW[i][j] && W[i][j] ){
                _ = true;
                BB[i+1][j] = true;
                WW[i+1][j] = true;
            }
        }
        if( x && _ ){
            ret += '?';
        }
        else if( x ){
            ret += 'X';
        }
        else if( _ ){
            ret += '_';
        }
    }
/*
    cout << "BBlack :" << endl;
    for( int i = 0; i < n; i ++ ){
        for( int j = 0; j <= k; j ++ ){
            cout << BB[i][j] << ' ';
        }
        cout << endl;
    }
    cout << "WWhite :" << endl;
    for( int i = 0; i < n; i ++ ){
        for( int j = 0 ;j <= k; j ++ ){
            cout << WW[i][j] << ' ';
        }
        cout << endl;
    }

*/
    return ret;
}
/*
int main()
{
    string ans;
    ans = solve_puzzle( "..........", {3,4} );
    cout << ans;
    return 0;
}
*/

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