Submission #1022873

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022873		parsadox2	Paint By Numbers (IOI16_paint)	C++17	100 / 100	191 ms	46488 KiB

paint

#include "paint.h"

#include <cstdlib>
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10 , K = 110;
int n , pw[N] , pb[N] , k;
bool dp[N][K] , reach[N][K] , W[N] , B[N];
string s;

bool can(int id , int bl)
{
    if(id + bl > n)
        return false;
    int tmp = pw[id + bl - 1];
    if(id > 0)
        tmp -= pw[id - 1];
    if(tmp != 0)
        return false;
    if(id + bl < n && s[id + bl] == 'X')
        return false;
    return true;
}

string solve_puzzle(string ss, vector<int> c) {
    n = ss.size();
    k = c.size();
    s = ss;
    dp[n][k] = true;
    pw[0] = (s[0] == '_' ? 1 : 0);
    pb[0] = (s[0] == 'X' ? 1 : 0);
    for(int i = 1 ; i < n ; i++)
    {
        pw[i] = pw[i - 1];
        pb[i] = pb[i - 1];
        pw[i] += (s[i] == '_' ? 1 : 0);
        pb[i] += (s[i] == 'X' ? 1 : 0);
    }
    for(int i = n - 1 ; i >= 0 ; i--)
    {
        if(s[i] != 'X')
            dp[i][k] = dp[i + 1][k];
        for(int j = 0 ; j < k ; j++)
        {
            if(s[i] != 'X')
                dp[i][j] = dp[i + 1][j];
            if(can(i , c[j]))
                dp[i][j] |= dp[min(n , i + c[j] + 1)][j + 1];
        }
    }
    reach[0][0] = true;
    int las = -1;
    for(int i = 0 ; i < n ; i++)
    {
        if(las >= i)
            B[i] = true;
        for(int j = 0 ; j <= k ; j++)  if(reach[i][j])
        {
            //cout << i << " : " << j << endl;
            if(dp[i + 1][j] && s[i] != 'X')
            {
                W[i] = true;
                reach[i + 1][j] = true;
            }
            if(j != k && dp[min(i + c[j] + 1 , n)][j + 1] && can(i , c[j]))
            {
                B[i] = true;
                W[i + c[j]] = true;
                reach[min(i + c[j] + 1 , n)][j + 1] = true;
                las = max(las , i + c[j] - 1);
            }
        }
        if(!W[i])
            s[i] = 'X';
        else if(!B[i])
            s[i] = '_';
        else
            s[i] = '?';
    }
    return s;
}

• 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