Submission #392941

#	Time	Username	Problem	Language	Result	Execution time	Memory
392941		blue	Paint By Numbers (IOI16_paint)	C++17	7 / 100	1 ms	204 KiB

paint

#include "paint.h"
#include <iostream>
#include <vector>
#include <string>
using namespace std;

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

    int W[n+1], B[n+1];
    W[0] = B[0] = 0;
    for(int i = 1; i <= n; i++)
    {
        W[i] = W[i-1];
        B[i] = B[i-1];
        if(s[i-1] == 'X') B[i]++;
        else if(s[i-1] == '_') W[i]++;
    }


    int cover_pref[n+1][k+1]; //can the first i positions accomodate the first j blocks

    cover_pref[0][0] = 1;
    for(int j = 1; j <= k; j++) cover_pref[0][j] = 0;

    for(int i = 1; i <= n; i++)
    {
        cover_pref[i][0] = (B[i] == 0);
        for(int j = 1; j <= k; j++)
        {
            cover_pref[i][j] = 0;

            cover_pref[i][j] |= (B[i] - B[i-1] == 0) && cover_pref[i-1][j];

            cover_pref[i][j] |= (j == 1) && (i == c[j-1]) && (W[i] == 0);

            cover_pref[i][j] |= (i > c[j-1])
                                && (W[i] - W[i-c[j-1]] == 0)
                                && (B[i-c[j-1]] - B[i-c[j-1]-1] == 0)
                                && cover_pref[i - c[j-1] - 1][j-1];
        }
    }

    vector<int> max_pref(n+2, 0);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= k; j++)
            if(cover_pref[i][j])
                max_pref[i] = max(max_pref[i], j);
    max_pref[n+1] = max_pref[n];












    int cover_suff[n+2][k+2]; //can the suffix starting from i accomodate j last j blocks

    cover_suff[n+1][0] = 1;
    for(int j = 1; j <= k; j++) cover_suff[n+1][j] = 0;

    // cerr << n+1 << '\n';
    // cerr << cover_suff[11][2] << '\n';

    for(int i = n; i >= 1; i--)
    {
        cover_suff[i][0] = (B[n] - B[i-1] == 0);

        // cerr << cover_suff[i][0] << ' ';

        for(int j = 1; j <= k; j++)
        {
            cover_suff[i][j] = 0;

            // cerr << i << ' ' <<  j << cover_suff[i+1][j];
            cover_suff[i][j] |= (B[i] - B[i-1] == 0) && cover_suff[i+1][j];

            // cerr << cover_suff[i][j] << '|';

            cover_suff[i][j] |= (j == 1) && (i + c[k-j] - 1 == n) && (W[n] - W[i-1] == 0);

            // cerr << cover_suff[i][j] << '|';

            cover_suff[i][j] |= (i + c[k-j] - 1 < n)
                                && (W[i + c[k-j] - 1] - W[i-1] == 0)
                                && (B[i + c[k-j]] - B[i + c[k-j] - 1] == 0)
                                && cover_suff[i + c[k-j] + 1][j-1];

            // cerr << cover_suff[i][j] << ' ';
        }
        // cerr << '\n';
    }


    vector<int> max_suff(n+2, 0);
    for(int i = n; i >= 1; i--)
        for(int j = 1; j <= k; j++)
            if(cover_suff[i][j])
                max_suff[i] = max(max_suff[i], j);

    max_suff[0] = max_suff[1];


    vector<int> canbeWhite(n+1, 0);
    for(int i = 1; i <= n; i++)
    {
        if(B[i] - B[i-1] != 0) continue;
        for(int j = 0; j <= k; j++)
            if(cover_pref[i-1][j] && cover_suff[i+1][k-j])
                canbeWhite[i] = 1;
    }

    vector<int> ptr(n+1, 0);
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= k; j++)
        {
            // cerr << '\n';
            // cerr << i << ' ' << j << '\n';
            // cerr << 'A';
            if(W[i + c[j-1] - 1] > W[i-1]) continue;
            // cerr << 'B';
            if(B[i-1] > B[max(0, i-2)]) continue;
            // cerr << 'C';
            if(i+c[j-1]-1 < n && B[i+c[j-1]] > B[i+c[j-1]-1]) continue;
            // cerr << 'D';
            if(i > 1 && !cover_pref[i-2][j-1]) continue;
            // cerr << 'E';
            if(!cover_suff[i + c[j-1] + 1][k-j]) continue;
            // cerr << 'F';
            ptr[i] = max(ptr[i], i + c[j-1] - 1);
        }
    }
    // cerr << '\n';

    // for(int i = 1; i <= n; i++)
    //     cerr << ptr[i] << ' ';
    //     cerr << '\n';

    vector<int> canbeBlack(n+1, 0);
    int p = 0;
    for(int i = 1; i <= n; i++)
    {
        p = max(p, ptr[i]);
        if(i <= p)
            canbeBlack[i] = 1;
    }

    // for(int i = 1; i <= n; i++) cerr << canbeWhite[i] << ' ';
    // cerr << '\n';
    // for(int i = 1; i <= n; i++) cerr << canbeBlack[i] << ' ';
    // cerr << '\n';

    string res;
    for(int i = 1; i <= n; i++)
    {
        if(canbeBlack[i] && canbeWhite[i]) res.push_back('?');
        else if(canbeBlack[i]) res.push_back('X');
        else res.push_back('_');
    }

    return res;
}

• Subtask 1: 7 / 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