Submission #856678

#	Time	Username	Problem	Language	Result	Execution time	Memory
856678		LucaIlie	Paint By Numbers (IOI16_paint)	C++17	100 / 100	309 ms	43592 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], canBeB[MAX_N + 4];
int spB[MAX_N + 4], spW[MAX_N + 4], black[MAX_N + 4];

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];
        }
    }

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

    int sum = 0;
    for ( int i = 2; i <= n + 1; i++ ) {
        sum += black[i];
        canBeB[i] = (sum > 0);
    }

    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]);

        if ( canBeB[i] && canBeW )
            ans += '?';
        else if ( canBeB[i] )
            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: 10 / 10