Submission #712551

#	Time	Username	Problem	Language	Result	Execution time	Memory
712551		neki	Paint By Numbers (IOI16_paint)	C++14	100 / 100	312 ms	42776 KiB

paint

#include "paint.h"
 
#include <bits/stdc++.h>
using namespace std;
const int mn = 200100;
const int mk = 110;
bool dl[mk][mn], dr[mk][mn];
int ps[mn], cX[mn], c_[mn];
string solve_puzzle(std::string s, std::vector<int> c)
{
    const int n = s.size(), k = c.size();
    for (int i = n - 1; i >= 0; --i)
        ps[i] = ps[i + 1] + (s[i] == '_');
 
    for (int b = 0; b < k; ++b)
    {
        bool can = 0;
        for (int i = 0; i < n; ++i)
            if (i - c[b] + 1 >= 0)
            {
                if (b == 0)
                {
                    if (i - c[b] >= 0 && s[i - c[b]] == 'X')
                        break;
                    if (ps[i - c[b] + 1] - ps[i + 1] == 0)
                        dl[b][i] = 1;
                }
                else if (i - c[b] - 1 >= 0)
                {
                    if (s[i - c[b]] == 'X')
                        can = 0;
                    if (s[i - c[b]] != 'X' && dl[b - 1][i - c[b] - 1])
                        can = 1;
                    if (can && ps[i - c[b] + 1] - ps[i + 1] == 0)
                        dl[b][i] = 1;
                }
            }
    }
 
    for (int b = k - 1; b >= 0; --b)
    {
        bool can = 0;
        for (int i = n - 1; i >= 0; --i)
            if (i + c[b] - 1 < n)
            {
                if (b == k - 1)
                {
                    if (i + c[b] < n && s[i + c[b]] == 'X')
                        break;
                    if (ps[i] - ps[i + c[b]] == 0)
                        dr[b][i] = 1;
                }
                else if (i + c[b] + 1 >= 0)
                {
                    if (s[i + c[b]] == 'X')
                        can = 0;
                    if (s[i + c[b]] != 'X' && dr[b + 1][i + c[b] + 1])
                        can = 1;
                    if (can && ps[i] - ps[i + c[b]] == 0)
                        dr[b][i] = 1;
                }
            }
    }
 
    /*cout << "k:" << k << endl;
    for (int b = 0; b < k; ++b)
    {
        cout << b << ": " << endl;
        for (int i = 0; i < n; ++i)
            cout << dr[b][i] << " ";
        cout << endl;
    }*/
 
    for (int b = 0; b < k; ++b)
        for (int i = 0; i < n; ++i)
            if (i - c[b] + 1 >= 0 && dl[b][i] && dr[b][i - c[b] + 1])
                ++cX[i - c[b] + 1], --cX[i + 1];
    for (int i = 1; i < n; ++i)
        cX[i] += cX[i - 1];
 
    for (int b = 0; b < k; ++b)
    {
        for (int i = 0; i < n; ++i)
        {
            if (s[i] != 'X' && i && dl[b][i - 1])
                dl[b][i] = 1;
        }
        for (int i = n - 1; i >= 0; --i)
        {
            if (s[i] != 'X' && i + 1 < n && dr[b][i + 1])
                dr[b][i] = 1;
        }
    }
    for(int b = 0; b < k; ++b)
    {
        for (int i = 0; i < n; ++i)
            if (b + 1 < k && i - 1 >= 0 && i + 1 < n && dl[b][i - 1] && dr[b + 1][i + 1] && s[i] != 'X')
                ++c_[i];
    }
    for (int i = n - 1; i >= 0; --i)
    {
        if (s[i] == 'X')
            break;
        if (i - 1 >= 0 && dl[k - 1][i - 1])
            ++c_[i];
    }
    for (int i = 0; i < n; ++i)
    {
        if (s[i] == 'X')
            break;
        if (i + 1 < n && dr[0][i + 1])
            ++c_[i];
    }
 
    string ans(n, '.');
    for (int i = 0; i < n; ++i)
        ans[i] = (cX[i] && c_[i] ? '?' : cX[i] ? 'X'
                                               : '_');
 
    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: 10 / 10