Submission #856673

#	Time	Username	Problem	Language	Result	Execution time	Memory
856673		LucaIlie	Paint By Numbers (IOI16_paint)	C++17	0 / 100	1 ms	4444 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] - spW[l - 1];
}

int sumB( int l, int r ) {
    return spB[r] - 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] == '_');
    }

    cout << s << "\n";
    for ( int i = 0; i <= n + 3; i++ ) {
        sePoateLR[i][0] = (sumB( 0, 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];
        }
    }

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

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:17:30: warning: array subscript -1 is below array bounds of 'int [200002]' [-Warray-bounds]
   17 |     return spB[r] - spB[l - 1];
      |                     ~~~~~~~~~^

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