Submission #290157

#	Time	Username	Problem	Language	Result	Execution time	Memory
290157		Kastanda	Paint By Numbers (IOI16_paint)	C++11	32 / 100	1 ms	512 KiB

paint

// M
#include<bits/stdc++.h>
#include "paint.h"
using namespace std;
const int N = 200005, K = 109;
int n, k, C[N], W[N], dp[N][K], pd[N][K], CW[N], CB[N], NW[N];
string S;

string solve_puzzle(string _S, vector< int > _C)
{
        n = (int)_S.size();
        k = (int)_C.size();
        S = "_" + _S;
        for (int i = 1; i <= k; i ++)
                C[i] = _C[i - 1];

        for (int i = 1; i <= n; i ++)
                W[i] = W[i - 1] + (S[i] == '_');

        int last = n;
        while (last && S[last] != 'X')
                last --;
        last = max(last, 1);

        int first = 1;
        while (first <= n && S[first] != 'X')
                first ++;
        first = min(first, n);

        for (int j = 1; j <= k; j ++)
                for (int i = C[j]; i <= n; i ++)
                        if (W[i] - W[i - C[j]] == 0)
                        {
                                if (j == 1)
                                {
                                        if (first > i - C[j])
                                                dp[i][j] = 1;
                                }
                                else if (i > C[j] && S[i - C[j]] != 'X' && dp[i - C[j] - 1][j - 1])
                                        dp[i][j] = 1;
                        }

        for (int j = k; j; j --)
                for (int i = n - C[j] + 1; i; i --)
                        if (W[i + C[j] - 1] - W[i - 1] == 0)
                        {
                                if (j == k)
                                {
                                        if (last < i + C[j])
                                                pd[i][j] = 1;
                                }
                                else if (i <= n - C[j] && S[i + C[j]] != 'X' && pd[i + C[j] + 1][j + 1])
                                        pd[i][j] = 1;
                        }
        for (int j = 1; j <= k; j ++)
                for (int i = n; i; i --)
                        if (S[i] != 'X')
                                pd[i][j] |= pd[i + 1][j];

        for (int j = 1; j < k; j ++)
                for (int i = 1; i <= n; i ++)
                        if (dp[i][j] && S[i + 1] != 'X' && pd[i + 2][j + 1])
                                CB[i - C[j] + 1] ++, CB[i + 1] --;

        for (int i = last; i <= n; i ++)
                if (dp[i][k])
                        CB[i - C[k] + 1] ++, CB[i + 1] --, CW[i + 1] ++;

        for (int j = 1; j <= k; j ++)
                for (int i = 1; i <= n; i ++)
                        if (S[i] != 'X')
                                dp[i][j] |= dp[i - 1][j];

        for (int j = 1; j < k; j ++)
                for (int i = 1; i <= n; i ++)
                        if (S[i] != 'X' && dp[i - 1][j] && pd[i + 1][j + 1])
                                CW[i] ++, CW[i + 1] --;

        for (int i = 1; i <= first; i ++)
                if (pd[i][1])
                        CW[1] ++, CW[i] --;

        string Rs;
        for (int i = 1; i <= n; i ++)
        {
                CW[i] += CW[i - 1];
                CB[i] += CB[i - 1];
                if (CB[i] && CW[i])
                        Rs += "?";
                else if (CB[i])
                        Rs += "X";
                else
                        Rs += "_";
        }
        return Rs;
}

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