Submission #92623

#	Time	Username	Problem	Language	Result	Execution time	Memory
92623		kitsu_hi	Paint By Numbers (IOI16_paint)	C++14	32 / 100	2 ms	892 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
#define nl '\n'

int frsB = -1;
int dp[2005][105][3];
int Black[2005];
bool White[2005];
int c1[105];

bool used[2005][105][2];

void find ( string ss ) {
    int ll = ss.size();
    for ( int i = 0; i < ll; i++ ) {
        if ( ss[i] == 'X' && frsB == -1 ) {
            frsB = i;
        }
    }
    if ( frsB == -1 ) {
        frsB = 1000000000;
    }
}

void go ( int clr, int num, int pos ) {
    if( used[pos][num][clr] != 0 ) return;
    used[pos][num][clr] = 1;
    if( num == 0 && clr == 1 ) return;
    if( pos < 0 ) return;
    if ( clr == 0 ) {
        White[pos] = 1;
        if ( dp[pos - 1][num][0] == 1 ) go( 0, num, pos - 1);
        if ( dp[pos - 1][num][1] == 1 ) go( 1, num, pos - 1);
        return;
    }
    if ( clr == 1 ) {
        Black[pos - c1[num - 1] + 1]++;
        Black[pos + 1]--;
        go ( 0, num - 1, pos - c1[num - 1] );
        return;
    }
}

string solve_puzzle( string s, vector<int> c) {
    int n = s.size();
    int k = c.size();
    for ( int i = 0; i < k; i++ ) {
        c1[i] = c[i];
    }
    find ( s );
    
    int cntW = 0;
    for ( int i = 0; i < c[0]; i++ ) {
        if ( s[i] == '_' ) {
            cntW++;
        }
    }
    for ( int i = 0; i < c[0] - 1; i++ ) {
        dp[i][1][1] = 0;
    }
    for ( int i = 0; i <= min( frsB, n - c[0] ); i++ ){
        if ( cntW == 0 ) {
            dp[c[0] + i - 1][1][1] = 1;
        }
        else {
            dp[c[0] + i - 1][1][1] = 0;
        }
        if ( s[c[0] + i] == '_' ) {
            cntW--;
        }
        if ( s[i] == '_' ) {
            cntW--;
        }
    }
    for ( int i = min( frsB, n - c[0] ) + c[0]; i < n; i++ ) {
        dp[i][1][1] = 0;
    }
    for ( int i = 0; i < c[0]; i++ ) {
        dp[i][1][0] = 0;
    }
    if ( dp[c[0] - 1][1][1] == 1 && s[c[0]] != 'X' ) {
        dp[c[0]][1][0] = 1;
    } 
    for ( int i = c[0] + 1; i < n; i++ ){
        if ( s[i] == 'X' ) {
            dp[i][1][0] = 0;
        }
        else {
            if ( dp[i - 1][1][0] || dp[i - 1][1][1] ) {
                dp[i][1][0] = 1;
            }
            else {
                dp[i][1][0] = 0;
            }
        }
    }

    for ( int i = 2; i <= k; i++ ) {
        cntW = 0;
        for ( int j = 0; j < c[i - 1]; j++ ) {
            if ( s[j] == '_' ) {
                cntW++;
            }
        }
        for ( int j = 0; j < c[i - 1]; j++ ) {
            dp[j][i][1] = 0;
        }
        for ( int j = c[i - 1]; j < n; j++ ) {
            if ( s[j] == '_' ) {
                cntW++;
            }
            if ( s[j - c[i - 1]] == '_' ) {
                cntW--;
            }
            dp[j][i][1] = 0;
            if ( cntW == 0 && dp[j - c[i - 1]][i - 1][0] ) {
                dp[j][i][1] = 1;
            } 
        
        }
        dp[0][i][0] = 0;
        for ( int j = 1; j < n; j++ ) {
            dp[j][i][0] = 0;
            if ( s[j] != 'X' && (dp[j - 1][i][1] || dp[j - 1][i][0]) ) {
                dp[j][i][0] = 1;
            }
        }
    }
    memset( Black, 0, sizeof Black);
    memset( White, 0, sizeof White);
    memset( used, 0, sizeof used );

    if( dp[n - 1][k][1] == 1 ) go( 1, k, n - 1);
    if( dp[n - 1][k][0] == 1 ) go( 0, k, n - 1);

    int cnt = 0;
    for ( int i = 0; i < n; i++ ) {
        cnt += Black[i];
        if ( cnt > 0 ) Black[i] = 1;
        else Black[i] = 0;
    }
    for ( int i = 0; i < n; i++ ) {
        if ( Black[i] == 1 && White[i] == 1 ){
            s[i] = '?';
        }
        if ( Black[i] == 1 && White[i] == 0 ){
            s[i] = 'X';
        }
        if ( Black[i] == 0 && White[i] == 1 ){
            s[i] = '_';
        }
    }
    return s;
}

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