제출 #856676

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
856676		LucaIlie	Paint By Numbers (IOI16_paint)	C++17	90 / 100	2064 ms	42060 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5;
const int MAX_K = 100;

bool sePoateLR[MAX_N + 4][MAX_K + 1], sePoateRL[MAX_N + 4][MAX_K + 1];
int spB[MAX_N + 2], spW[MAX_N + 2];

int sumW( int l, int r ) {
    return spW[r] - (l == 0 ? 0 : spW[l - 1] );
}

int sumB( int l, int r ) {
    return spB[r] - (l == 0 ? 0 : spB[l - 1] );
}

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

    s = "_" + s + "_";
    s = "." + s + ".";
    reverse( c.begin(), c.end() );
    c.push_back( 0 );
    reverse( c.begin(), c.end() );
    c.push_back( 0 );

    for ( int i = 1; i <= n + 3; i++ ) {
        spB[i] = spB[i - 1] + (s[i] == 'X');
        spW[i] = spW[i - 1] + (s[i] == '_');
    }

    for ( int i = 0; i <= n + 3; i++ ) {
        sePoateLR[i][0] = (sumB( 1, i ) == 0);
        for ( int j = 1; j <= k + 1; j++ )  {
            if ( i - c[j] < 0 ) {
                sePoateLR[i][j] = false;
                continue;
            }
            if ( sumW( i - c[j] + 1, i ) == 0 && s[i - c[j]] != 'X' )
                sePoateLR[i][j] = sePoateLR[i - c[j] - 1][j - 1];
            else
                sePoateLR[i][j] = false;
        }
        if ( s[i] != 'X' && i >= 1 ) {
            for ( int j = 0; j <= k + 1; j++ )
                sePoateLR[i][j] |= sePoateLR[i - 1][j];
        }
    }

    for ( int i = n + 3; i >= 0; i-- ) {
        sePoateRL[i][k + 1] = (sumB( i, n + 3 ) == 0);
        for ( int j = k; j >= 0; j-- )  {
            if ( i + c[j] > n + 3 ) {
                sePoateRL[i][j] = false;
                continue;
            }
            if ( sumW( i, i + c[j] - 1 ) == 0 && s[i + c[j]] != 'X' ) {
                if ( i + c[j] == n + 1 )
                    sePoateRL[i][j] = (j == k);
                else
                    sePoateRL[i][j] = sePoateRL[i + c[j] + 1][j + 1];
            } else
                sePoateRL[i][j] = false;
        }
        if ( s[i] != 'X' && i <= n + 2 ) {
            for ( int j = 0; j <= k + 1; j++ )
                sePoateRL[i][j] |= sePoateRL[i + 1][j];
        }
    }

    /*printf( "LR\n" );
    for ( int i = 0; i <= n + 3; i++ ) {
        printf( "%d ", i );
        for ( int j = 0; j <= k + 1; j++ )
            printf( "%d", sePoateLR[i][j] );
        printf( "\n" );
    }
    printf( "RL\n" );
    for ( int i = n + 3; i >= 0; i-- ) {
        printf( "%d ", i );
        for ( int j = k + 1; j >= 0; j-- )
            printf( "%d", sePoateRL[i][j] );
        printf( "\n" );
    }*/

    string ans = "";
    for ( int i = 2; i <= n + 1; i++ ) {
        if ( s[i] != '.' ) {
            ans += s[i];
            continue;
        }

        bool canBeW = false;
        for ( int j = 0; j <= k; j++ )
            canBeW |= (sePoateLR[i - 1][j] & sePoateRL[i + 1][j + 1]);

        bool canBeB = false;
        for ( int j = 1; j <= k; j++ ) {
            for ( int l = i; l > i - c[j] && l >= 2; l-- ) {
                int r = (i + (c[j] - (i - l)) - 1);
                if ( r <= n + 2 && sumW( l, r ) == 0 && s[l - 1] != 'X' && s[r + 1] != 'X' )
                    canBeB |= (sePoateLR[l - 2][j - 1] & sePoateRL[r + 2][j + 1]);
            }
        }

        if ( canBeB && canBeW )
            ans += '?';
        else if ( canBeB )
            ans += 'X';
        else if ( canBeW )
            ans += "_";
        else
            ans += 'l';
    }

    return ans;
}

• 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: 0 / 10