Submission #44960

#	Time	Username	Problem	Language	Result	Execution time	Memory
44960		RayaBurong25_1	Paint By Numbers (IOI16_paint)	C++17	100 / 100	849 ms	340112 KiB

paint

#include "paint.h"
#include <cstdlib>
#include <cassert>
#include <stdio.h>
int mustB[200005];
int QmustW[200005];
int Pre[200005][105];
int canEnd[200005][105];
int QcanEnd[200005][105];
int Suf[200005][105];
int canW[200005];
int canB[200005];
std::string Ans;
int min(int a, int b)
{
    return (a < b)?a:b;
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
    int i, j, l, n = s.size(), k = c.size();
    for (i = 1; i <= n; i++)
    {
        mustB[i] = (s[i - 1] == 'X');
        QmustW[i] = (s[i - 1] == '_') + QmustW[i - 1];
    }
    // printf("Pre\n");
    for (i = 0; i <= n; i++)
    {
        for (j = 0; j <= k; j++)
        {
            if (i == 0 && j == 0)
                Pre[i][j] = 1;
            else if (j == 0)
                Pre[i][j] = Pre[i - 1][j] && !mustB[i];
            else if (i == 0)
                Pre[i][j] = 0;
            else
            {
                if (j == 1)
                {
                    canEnd[i][j] = ((i - c[j - 1] >= 0) && Pre[i - c[j - 1]][j - 1] && (QmustW[i] - QmustW[i - c[j - 1]] == 0));
                    Pre[i][j] = ((Pre[i - 1][j] && !mustB[i]) || canEnd[i][j]);
                }
                else
                {
                    canEnd[i][j] = ((i - c[j - 1] - 1 >= 0) && Pre[i - c[j - 1] - 1][j - 1] && !mustB[i - c[j - 1]] && (QmustW[i] - QmustW[i - c[j - 1]] == 0));
                    Pre[i][j] = ((Pre[i - 1][j] && !mustB[i]) || canEnd[i][j]);
                }
            }
            // printf("%d", Pre[i][j]);
        }
        // printf("\n");
    }
    // printf("Suf\n");
    for (i = n + 1; i > 0; i--)
    {
        for (j = 0; j <= k; j++)
        {
            if (i == n + 1 && j == 0)
                Suf[i][j] = 1;
            else if (j == 0)
                Suf[i][j] = Suf[i + 1][j] && !mustB[i];
            else if (i == n + 1)
                Suf[i][j] = 0;
            else
            {
                if (j == 1)
                    Suf[i][j] = ((Suf[i + 1][j] && !mustB[i]) || ((i + c[k - j] <= n + 1) && Suf[i + c[k - j]][j - 1] && (QmustW[i + c[k - j] - 1] - QmustW[i - 1] == 0)));
                else
                    Suf[i][j] = ((Suf[i + 1][j] && !mustB[i]) || ((i + c[k - j] + 1 <= n + 1) && Suf[i + c[k - j] + 1][j - 1] && !mustB[i + c[k - j]] && (QmustW[i + c[k - j] - 1] - QmustW[i - 1] == 0)));
            }
            // printf("%d", Suf[i][j]);
        }
        // printf("\n");
    }
    // printf("canEnd\n");
    for (i = 0; i <= n; i++)
    {
        for (j = 1; j <= k; j++)
        {
            if (j == k)
                canEnd[i][j] = canEnd[i][j] && Suf[i + 1][0];
            else
                canEnd[i][j] = canEnd[i][j] && !mustB[i + 1] && Suf[i + 2][k - j];
            // printf("%d", canEnd[i][j]);

            if (i > 0)
                QcanEnd[i][j] = QcanEnd[i - 1][j] + canEnd[i][j];
        }
        // printf("\n");
    }
    for (i = 1; i <= n; i++)
    {
        for (j = 0; j <= k; j++)
        {
            canW[i] |= Pre[i - 1][j] && Suf[i + 1][k - j] && !mustB[i];
        }
        for (j = 1; j <= k; j++)
        {
            canB[i] |= (QcanEnd[min(n, i + c[j - 1] - 1)][j] - QcanEnd[i - 1][j] > 0);
        }
        // printf("i%d canW%d canB%d\n", i, canW[i], canB[i]);
    }
    for (i = 1; i <= n; i++)
    {
        if (canW[i] && canB[i])
            Ans.push_back('?');
        else if (canW[i])
            Ans.push_back('_');
        else if (canB[i])
            Ans.push_back('X');
        else
            assert(1 == 0);
    }
    return Ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:19:15: warning: unused variable 'l' [-Wunused-variable]
     int i, j, l, n = s.size(), k = c.size();
               ^

• 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