Submission #62849

#	Time	Username	Problem	Language	Result	Execution time	Memory
62849		Kubalionzzale	Paint By Numbers (IOI16_paint)	C++14	90 / 100	2052 ms	212916 KiB

paint

#include "paint.h"

#include <cstdlib>
#include <iostream>
#include <string>



    std::string ans = "";

    int prefix[200010] = { 0 }, suffix[200010] = { 0 };

    bool dp[200010][110] = { 0 }, dprev[200010][110] = { 0 };
    bool flag = 1;
int leftBiggest[200010][110] = { 0 };
    int rightBiggest[200010][110] = { 0 };
    int valq = 200005;
    int biggest;

    int sum = 0;
    int howMuch;
int notx[200010] = { 0 }, xs[200010];
    int length;
    bool can;
std::string solve_puzzle(std::string str, std::vector<int> c) {

    int k = c.size();
    int n = str.size();
    if (str[0] == '_')
        prefix[0] = 1;

    if (str[n - 1] == '_')
        suffix[n - 1] = 1;

    for (int i = 1; i < n; ++i)
    {
        prefix[i] = prefix[i - 1];

        if (str[i] == '_')
            ++prefix[i];
    }

    for (int i = n - 2; i >= 0; --i)
    {
        suffix[i] = suffix[i + 1];

        if (str[i] == '_')
            ++suffix[i];
    }

    for (int i = 0; i < n; ++i)
    {
        if (str[i] == 'X')
            flag = 0;

        dp[i][0] = flag;
    }
    flag = 1;

    for (int i = n - 1; i >= 0; --i)
    {
        if (str[i] == 'X')
            flag = 0;

        dprev[i][k] = flag;
    }

    dprev[n][k] = 1;



    for (int i = 1; i <= k; ++i)
    {
        howMuch = c[i - 1];
        sum += howMuch;

        if (i == 1)
        {
            if (prefix[howMuch - 1] == 0)
            {
                dp[howMuch - 1][i] = 1;
            }
        }

        for (int j = sum; j < n; ++j)
        {
            if (str[j] != 'X')
            {
                dp[j][i] = dp[j - 1][i];
            }

            if (i == 1)
            {
                if (prefix[j] - prefix[j - howMuch] == 0)
                    dp[j][i] = std::max(dp[j][i], dp[j - howMuch][i - 1]);
                continue;
            }

            if (prefix[j] - prefix[j - howMuch] == 0 && str[j - howMuch] != 'X')
            {
                dp[j][i] = std::max(dp[j][i], dp[j - howMuch - 1][i - 1]);
            }
        }
    }

    sum = 0;
    for (int i = k - 1; i >= 0; --i)
    {
        howMuch = c[i];
        sum += howMuch;

        if (i == k - 1)
        {
            if (suffix[n - howMuch] == 0)
            {
                dprev[n - howMuch][i] = 1;
            }
        }

        for (int j = n - sum - 1; j >= 0; --j)
        {
            if (str[j] != 'X')
            {
                dprev[j][i] = dprev[j + 1][i];
            }

            if (i == k - 1)
            {
                if (suffix[j] - suffix[j + howMuch] == 0)
                    dprev[j][i] = std::max(dprev[j][i], dprev[j + howMuch][i + 1]);

                continue;
            }

            if (suffix[j] - suffix[j + howMuch] == 0 && str[j + howMuch] != 'X')
            {
                dprev[j][i] = std::max(dprev[j][i], dprev[j + howMuch + 1][i + 1]);
            }
        }
    }

    for (int i = k - 1; i >= 0; --i)
    {
        biggest = valq;

        if (i == k - 1)
            biggest = n;

        for (int j = n - 1; j >= 0; --j)
        {
            rightBiggest[j][i] = biggest;

            if (dprev[j][i + 1] && biggest == valq)
                biggest = j;
            if (str[j] == 'X' && dprev[j][i + 1] != 1)
                biggest = valq;
            if (str[j] == 'X' && dprev[j][i + 1] == 1)
                biggest = j;
        }
    }

    for (int i = 1; i <= k; ++i)
    {
        biggest = valq;

        if (i == 1)
            biggest = -1;

        for (int j = 0; j < n; ++j)
        {
            leftBiggest[j][i] = biggest;

            if (dp[j][i - 1] && biggest == valq)
                biggest = j;
            if (str[j] == 'X' && dp[j][i - 1] != 1)
                biggest = valq;
            if (str[j] == 'X' && dp[j][i - 1] == 1)
                biggest = j;
        }
    }


    for (int i = 0; i < k; ++i)
    {
        length = c[i];
        if (length == n)
        {
            if (prefix[length - 1] == 0 && i == 0)
            {
                ++xs[0];
                --xs[length];
            }
        }
        else
        {
            if (i == 0)
            {
                if (dprev[length + 1][i + 1] && prefix[length - 1] == 0 && str[length] != 'X')
                {
                    ++xs[0];
                    --xs[c[i]];

                    ++notx[length];
                    --notx[rightBiggest[length][i]];
                }
            }

            if (i + 1 == k)
            {
                if (dp[n - length - 1][i] && suffix[n - length] == 0 && str[n - length - 1] != 'X')
                {
                    ++xs[n - length];
                    --xs[n];

                    ++notx[leftBiggest[n - length][i + 1] + 1];
                    --notx[n - length];
                }
            }
        }

        for (int j = c[i]; j < n - 1; ++j)
        {
            can = true;

            if (str[j - length] == 'X' || str[j + 1] == 'X')
            {
                can = false;
                continue;
            }

            if (j - length > 0)
            {
                if (dp[j - length - 1][i] == 0)
                {
                    can = false;
                    continue;
                }
            }

            if (j - length == 0 && i != 0)
            {
                can = false;
                continue;
            }

            if (n - j >= 2)
            {
                if (dprev[j + 2][i + 1] == 0)
                {
                    can = false;
                    continue;
                }
            }

            if (prefix[j] - prefix[j - c[i]] > 0)
            {
                can = false;
                continue;
            }

            if (can)
            {
                ++xs[j - length + 1];
                --xs[j + 1];

                ++notx[leftBiggest[j - length + 1][i + 1] + 1];
                --notx[j - length + 1];

                ++notx[j + 1];
                --notx[rightBiggest[j][i]];
            }
        }
    }

    int xsum = 0, notxsum = 0;
    for (int i = 0; i < n; ++i)
    {
        xsum += xs[i];
        notxsum += notx[i];

        if (xsum > 0 && notxsum > 0)
            ans += "?";
        else if (xsum > 0)
            ans += "X";
        else
            ans += "_";
    }

    return ans;
}

• 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: 0 / 10