제출 #62834

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
62834		Kubalionzzale	Paint By Numbers (IOI16_paint)	C++14	90 / 100	2021 ms	221720 KiB

paint

#include "paint.h"

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

std::string solve_puzzle(std::string str, std::vector<int> c) {
    int k = c.size();
    int n = str.size();

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

    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];
    }

    bool dp[200010][110] = { 0 }, dprev[200010][110] = { 0 };
    bool flag = 1;
    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;

    int sum = 0;

    for (int i = 1; i <= k; ++i)
    {
        int 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)
    {
        int 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]);
            }
        }
    }


    int leftBiggest[200010][110] = { 0 };
    int rightBiggest[200010][110] = { 0 };
    int valq = 200005;

    for (int i = k - 1; i >= 0; --i)
    {
        int 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)
    {
        int 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;
        }
    }

/*
    std::cout << "rightBiggest:\n";

    for (int i = 0; i < k; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            std::cout << rightBiggest[j][i] << " ";
        }

        std::cout << "\n";
    }

    for (int j = 0; j < n; ++j)
    {
        leftBiggest[j][0] = -1;
        rightBiggest[j][k] = n;
    }

    std::cout << "leftBiggest:\n";

    for (int i = 1; i <= k; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            std::cout << leftBiggest[j][i] << " ";
        }

        std::cout << "\n";
    }

    std::cout << "DP:\n";

    for (int i = 1; i <= k; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            std::cout << dp[j][i] << " ";
        }

        std::cout << "\n";
    }

    std::cout << "DPREV:\n";

    for (int i = 0; i < k; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            std::cout << dprev[j][i] << " ";
        }

        std::cout << "\n";
    }*/

    int notx[200010] = { 0 }, xs[200010];
    for (int i = 0; i < k; ++i)
    {
        int 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]];
               //     std::cout << "RIGHT: " << length << " " << rightBiggest[length][i] << "\n";
                }
            }

            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];

             //       std::cout << "LEFT: " << leftBiggest[n - length][i + 1] + 1 << " " << n - length << "\n";
                }
            }
        }

        for (int j = c[i]; j < n - 1; ++j)
        {
            bool 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)
            {/*
                std::cout << i << " " << j << "|\n";
                std::cout << "LEFT: " << leftBiggest[j - length + 1][i + 1] + 1 << " " << j - length + 1 << "\n";
                std::cout << "RIGHT: " << j + 1 << " " << rightBiggest[j][i] << "\n";*/
                ++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]];
            }
        }
    }

    std::string ans = "";

    int xsum = 0, notxsum = 0;
    for (int i = 0; i < n; ++i)
    {
 //       std::cout << xs[i] << " " << notx[i] << "\n";
        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