Submission #707701

#	Time	Username	Problem	Language	Result	Execution time	Memory
707701		benjaminkleyn	Paint By Numbers (IOI16_paint)	C++17	32 / 100	1 ms	312 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
typedef long long ll;

string calc(int n, vector<int> &c, int l, int r)
{
    string res(n, '?');

    int sum_l = 0, sum_r = 0;
    for (int i = l; i <= r; i++)
        sum_r += c[i];

    for (int i = l; i <= r; i++)
    {
        sum_r -= c[i];

        int L_dist = sum_l + (i - l);
        int R_dist = sum_r + (r - l + 1) - 1 - (i - l);

        int leftmost_l = L_dist;
        int leftmost_r = L_dist + c[i] - 1;

        int rightmost_l = n - R_dist - c[i];
        int rightmost_r = n - R_dist - 1;

        for (int j = rightmost_l; j <= leftmost_r; j++)
            res[j] = 'X';

        sum_l += c[i];
    }

    if (sum_l + (r - l + 1) - 1 == n)
    {
        for (int i = 0; i < n; i++)
            if (res[i] == '?')
                res[i] = '_';
    }

    return res;
}

int pref[200001] = {0};
int L[200001] = {0};
int R[200002] = {0};
string solve_puzzle(string s, vector<int> c) 
{
    int n = s.size(), k = c.size();
    s = "#" + s;

    pref[0] = 0;
    for (int i = 1; i <= n; i++)
        pref[i] = pref[i-1] + (s[i] == '_');

    for (int i = 0, l = 1, r = -1; i < k; i++)
    {
        l = r + 2, r = l + c[i] - 1;
        while (pref[r] - pref[l-1])
            l++, r++;
        L[r] = 1;
    }

    for (int i = k - 1, l = n + 2, r = n; i >= 0; i--)
    {
        r = l - 2, l = r - c[i] + 1;
        while (pref[r] - pref[l-1])
            l--, r--;
        R[l] = 1;
    }

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

    for (int i = n; i >= 1; i--)
        R[i] += R[i+1];

    string res = "";
    for (int l = 1, r; l <= n; l = r + 1)
    {
        r = l;
        if (s[l] == '_') 
        {
            res += "_";
            continue;
        }

        while (r + 1 <= n && s[r + 1] == s[l])
            r++;

        if (L[l-1] + R[r+1] >= k)
            res += string(r - l + 1, '?');
        else
            res += calc(r - l + 1, c, L[l-1], k - R[r+1] - 1);
    }
    

    return res;
}

Compilation message (stderr)

paint.cpp: In function 'std::string calc(int, std::vector<int>&, int, int)':
paint.cpp:21:13: warning: unused variable 'leftmost_l' [-Wunused-variable]
   21 |         int leftmost_l = L_dist;
      |             ^~~~~~~~~~
paint.cpp:25:13: warning: unused variable 'rightmost_r' [-Wunused-variable]
   25 |         int rightmost_r = n - R_dist - 1;
      |             ^~~~~~~~~~~

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