Submission #1044780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044780		fv3	Paint By Numbers (IOI16_paint)	C++14	59 / 100	1 ms	348 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>
using namespace std;

int N, M;

string solve_puzzle(string s, vector<int> c)
{
    N = s.size();
    M = c.size();

    vector<int> preSum(M);
    vector<int> sufSum(M, N);

    int l = 0;
    for (int i = 0; i < M; i++)
    {
        for (int j = l; j < l + c[i]; j++)
        {
            if (s[j] == '_')
                l = j + 1;
        } 
        preSum[i] = l;
        l += c[i] + 1;
    }

    int r = N - 1;
    for (int i = M - 1; i >= 0; i--)
    {
        for (int j = r; j > r - c[i]; j--)
        {
            if (s[j] == '_')
                r = j - 1;
        }
        sufSum[i] = r - c[i] + 1;
        r -= c[i] + 1;
    }

    string res = s;
    for (int i = 0; i < M; i++)
    {
        for (int j = sufSum[i]; j < preSum[i] + c[i]; j++)
            res[j] = 'X';
    }

    int cnt = 0;
    for (auto c : res)
        c=='X'&&cnt++;

    int sum = 0;
    for (auto n : c)
        sum += n;

    if (cnt == sum)
    {
        for (auto&c : res)
        {
            if (c == '.')
                c = '_';
        }
        return res;
    }

    for (auto&c : res)
    {
        if (c == '.')
            c = '?';
    }

    vector<int> lcnt(N);
    for (int i = 0; i < M; i++)
    {
        for (int j = preSum[i] + c[i] + 1; j < N; j++)
            lcnt[j]++;
    }
    vector<int> rcnt(N, M);
    for (int i = M-1; i >= 0; i--)
    {
        for (int j = sufSum[i] - 2; j >= 0; j--)
            rcnt[j]--;
    }

    s += "_";
    for (int l = 0; l < N;)
    {
        if ((l == 0 && s[0] == '.') || (s[l] == '_' && s[l+1] == '.'))
        {
            int r = s[l] == '.' ? 0 : ++l;
            while (s[r] == '.')
                r++;
        
            int len = r - l;   

            if (lcnt[l] >= rcnt[l])
            {
                bool ok = false;
                for (int i = max(0, rcnt[l]-1); i <= min(lcnt[l], M-1); i++)
                {
                    if (c[i] <= len)
                        ok = true;
                }

                if (!ok)
                {
                    for (int i = l; i < r; i++)
                    {
                        res[i] = '_';
                    }
                }
            }

            l = r;
        }
        else
            l++;
    }

    for (int i = 0; i < N - 2; i++)
    {
        if (res[i] == 'X' && res[i+1] == '?' && res[i+2] == 'X')
            res[i+1] = '_';
    }

    return res;
}

• 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