제출 #62865

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

paint

    #include "paint.h"
     
    #include <cstdlib>
    #include <iostream>
    #include <string>
#include <algorithm>
     
     
     
        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