Submission #290183

#	Time	Username	Problem	Language	Result	Execution time	Memory
290183		Kastanda	Paint By Numbers (IOI16_paint)	C++11	100 / 100	1442 ms	174848 KiB

paint

// M
#include<bits/stdc++.h>
#include "paint.h"
using namespace std;
const int N = 200015, K = 109;
int n, k, C[N], W[N], dp[N][K], pd[N][K], CW[N], CB[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] == '_');

        for (int i = 0; i <= n + 3 && S[i] != 'X'; i ++)
                dp[i][0] = 1;
        for (int i = n + 3; i >= 0 && S[i] != 'X'; i --)
                pd[i][k + 1] = 1;

        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)
                                        dp[i][j] = dp[i - C[j]][j - 1];
                                else if (i > C[j] && S[i - C[j]] != 'X' && dp[i - C[j] - 1][j - 1])
                                        dp[i][j] = 1;
                        }
                        if (S[i] != 'X')
                                dp[i][j] |= dp[i - 1][j];
                }

        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)
                                        pd[i][j] = pd[i + C[j]][j + 1];
                                else if (i <= n - C[j] && S[i + C[j]] != 'X' && pd[i + C[j] + 1][j + 1])
                                        pd[i][j] = 1;
                        }
                        if (S[i] != 'X')
                                pd[i][j] |= pd[i + 1][j];
                }

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

                        le &= (W[i] - W[i - C[j]] == 0);

                        if (le && S[i + 1] != 'X' && pd[i + 2][j + 1])
                                CB[i - C[j] + 1] ++, CB[i + 1] --;
                }

        for (int j = 0; 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] --;

        string Rs;
        for (int i = 1; i <= n; i ++)
        {
                CW[i] += CW[i - 1];
                CB[i] += CB[i - 1];
                if (S[i] != '.')
                        Rs += S[i];
                else 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: 27 / 27
• Subtask 5: 21 / 21
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10