Submission #1232188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232188		badge881	Paint By Numbers (IOI16_paint)	C++20	59 / 100	1 ms	328 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"

using namespace std;

const string type[4] = {"X", "_", ".", "?"};
inline int id(char c)
{
    switch (c)
    {
    case 'X':
        return 0;
    case '_':
        return 1;
    case '.':
        return 2;
    case '?':
        return 3;
    default:
        break;
    }
}

string solve_puzzle(string s, vector<int> c)
{
    vector<int> base;
    for (auto &i : s)
        base.push_back(id(i));

    int n = base.size();
    int k = c.size();

    auto isOk = [&](int l, int r)
    {
        bool valid = true;
        for (int idx = l; idx <= r; idx++)
            valid = valid && base[idx] != 1;
        return valid;
    };

    vector<bool> is_black(n, false), is_white(n, false);
    vector<int> min_pos(k, 0), max_pos(k, n - 1);

    for (int i = 0; i < k; i++)
    {
        min_pos[i] = i == 0 ? 0 : min_pos[i - 1] + c[i - 1] + 1;
        while (!isOk(min_pos[i], min_pos[i] - 1 + c[i]))
            min_pos[i]++;
    }

    for (int i = k - 1; i >= 0; i--)
    {
        max_pos[i] = i == k - 1 ? n - 1 : max_pos[i + 1] - c[i + 1] - 1;
        while (!isOk(max_pos[i] - c[i] + 1, max_pos[i]))
            max_pos[i]--;
    }

    vector<bool> touched(n, false);
    for (int i = 0; i < k; i++)
    {
        int L = max_pos[i] - c[i] + 1, R = min_pos[i] + c[i] - 1;

        for (int j = min_pos[i]; j <= max_pos[i]; j++)
        {
            if (base[j] == 1)
                continue;
            int cl = j, cr = j;
            while (cl > 0 && base[cl - 1] != 1)
                cl--;
            while (cr < n - 1 && base[cr + 1] != 1)
                cr++;
            if (cr - cl + 1 >= c[i])
                touched[j] = true;
        }

        if (L > R)
            continue;

        for (int j = L; j <= R; j++)
            is_black[j] = true;
    }

    for (int i = 0; i < k - 1; i++)
        for (int j = max_pos[i] + 1; j < min_pos[i + 1]; j++)
            is_white[j] = true;

    for (int i = 0; i < n; i++)
        if (!touched[i])
            is_white[i] = true;

    string ans;
    for (int i = 0; i < n; i++)
    {
        if (is_black[i] && !(is_white[i]))
            ans += "X";
        else if (is_white[i] && !(is_black[i]))
            ans += "_";
        else
            ans += "?";
    }
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'int id(char)':
paint.cpp:22:1: warning: control reaches end of non-void function [-Wreturn-type]
   22 | }
      | ^
paint.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10