Submission #501005

#	Time	Username	Problem	Language	Result	Execution time	Memory
501005		blue	Paint By Numbers (IOI16_paint)	C++17	100 / 100	591 ms	177520 KiB

paint

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

using vi = vector<int>;
using vvi = vector<vi>;
#define sz(x) int(x.size())

vi black_count, white_count;
// string s;

bool psbl_black(int a, int b)
{
    return white_count[b] - white_count[a-1] == 0;
}

bool psbl_white(int a, int b)
{
    return black_count[b] - black_count[a-1] == 0;
}

string solve_puzzle(string s, vi c_)
{
    // cerr << "called\n";
    int N = sz(s);
    int K = sz(c_);

    s = "z" + s + "z";
    vi c{0};
    for(int x: c_) c.push_back(x);

    black_count = vi(1+N, 0);
    white_count = vi(1+N, 0);
    for(int i = 1; i <= N; i++)
    {
        black_count[i] = black_count[i-1];
        white_count[i] = white_count[i-1];

        if(s[i] == 'X') black_count[i]++;
        else if(s[i] == '_') white_count[i]++;
    }

    // cerr << "A\n";


    vvi dp(1+N, vi(1+K, 0));
    dp[0][0] = 1;

    //dp[0][j >= 1] == 0

    for(int i = 1; i <= N; i++)
    {
        dp[i][0] = dp[i-1][0] && psbl_white(i, i);

        for(int j = 1; j <= K; j++)
        {
            dp[i][j] = dp[i-1][j] && psbl_white(i, i);
            if(i - c[j] >= 1)
                dp[i][j] |= psbl_black(i - c[j] + 1, i) && psbl_white(i - c[j], i - c[j]) && dp[i - c[j] - 1][j-1];
            else if(i - c[j] == 0)
                dp[i][j] |= psbl_black(1, i) && (j == 1);
        }
    }
    // cerr << "B\n";


    vvi rev_dp(1+N+1, vi(1+K+1, 0));
    rev_dp[N+1][K+1] = 1;

    for(int i = N; i >= 1; i--)
    {
        rev_dp[i][K+1] = rev_dp[i+1][K+1] && psbl_white(i, i);

        for(int j = K; j >= 1; j--)
        {
            rev_dp[i][j] = rev_dp[i+1][j] && psbl_white(i, i);
            if(i + c[j] <= N)
                rev_dp[i][j] |= psbl_black(i, i + c[j] - 1) && psbl_white(i + c[j], i + c[j]) && rev_dp[i + c[j] + 1][j+1];
            else if(i + c[j] == N+1)
                rev_dp[i][j] |= psbl_black(i, N) && (j == K);
        }
    }

    // cerr << "C\n";



    vi can_black(1+N, 0);
    vi can_white(1+N, 0);

    for(int i = 1; i <= N; i++)
    {
        for(int j = 0; j <= K; j++)
        {
            // cerr << i << ' ' << j << '\n';

            can_white[i] |= dp[i-1][j] && rev_dp[i+1][j+1] && psbl_white(i, i);
        }
    }

    // cerr << "D\n";

    vi black_delta(1+N+1, 0);


    for(int j = 1; j <= K; j++)
    {
        for(int i = 1; i + c[j] - 1 <= N; i++)
        {
            // cerr << j << ' ' << i << '\n';
            if((i-2 == -1 && j == 1) || (i-2 >= 0 && dp[i-2][j-1]))
            {
                // cerr << "A\n";
                if(s[i-1] != 'X')
                {
                    // cerr << "B\n";
                    // cerr << int(i + c[j] - 1 + 2 == N+2 && j == K) << '\n';
                    // cerr << i + c[j] - 1 + 2 << '\n';
                    if((i + c[j] - 1 + 2 == N+2 && j == K) || (i + c[j] - 1 + 2 <= N+1 && rev_dp[i + c[j] - 1 + 2][j+1]))
                    {
                        // cerr << "C\n";
                        if(s[i + c[j] - 1 + 1] != 'X')
                        {
                            if(psbl_black(i, i + c[j] - 1))
                            {

                                black_delta[i]++;
                                black_delta[i+c[j]]--;
                            }
                        }
                    }
                }
            }
        }
    }

    // cerr << "E\n";

    int cr = 0;
    for(int i = 1; i <= N; i++)
    {
        cr += black_delta[i];
        can_black[i] = (cr >= 1) && (s[i] != '_');
    }

    string res;
    for(int i = 1; i <= N; i++)
    {
        char c;
        if(can_black[i] && can_white[i]) c = '?';
        else if(can_black[i]) c = 'X';
        else if(can_white[i]) c = '_';

        res.push_back(c);
    }

    return res;
}

• 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