Submission #288733

#	Time	Username	Problem	Language	Result	Execution time	Memory
288733		IgorI	Paint By Numbers (IOI16_paint)	C++17	100 / 100	551 ms	165212 KiB

paint

#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define forn(i, n) for (int (i) = 0; (i) < (n); (i)++)

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long ll;

const int N = 200007;
const int K = 103;

int dpL[K][N];
int dpR[K][N];

int cnt_[N];
int prevX[N], nextX[N];

string solve_puzzle(string s, vector<int> c)
{
    s = "X." + s + ".X";
    int k = c.size();
    c.push_back(1);
    reverse(all(c));
    c.push_back(1);
    reverse(all(c));

    int n = s.size();
    for (int i = 1; i < s.size(); i++)
    {
        cnt_[i] = cnt_[i - 1] + (s[i] == '_');
    }
    for (int i = 1; i < s.size(); i++)
    {
        prevX[i] = prevX[i - 1];
        if (s[i] == 'X') prevX[i] = i;
    }
    nextX[s.size() - 1] = s.size() - 1;
    for (int i = s.size() - 2; i >= 0; i--)
    {
        nextX[i] = nextX[i + 1];
        if (s[i] == 'X') nextX[i] = i;
    }
    c[0] = 1, c[k + 1] = 1;
    dpL[0][0] = 1;
    dpL[k + 1][n - 1] = 1;
    dpR[0][0] = 1;
    dpR[k + 1][n - 1] = 1;
    for (int j = 1; j <= k; j++)
    {
        vector<int> pdp(n, -1);
        for (int i = 0; i < n; i++)
        {
            if (i) pdp[i] = pdp[i - 1];
            if (dpL[j - 1][i]) pdp[i] = i;
        }
        for (int i = 1; i < n; i++)
        {
            int L = i - c[j];
            if (L < 0 || s[L] == 'X') continue;
            if (cnt_[i] - cnt_[L] != 0) continue;
            int a = prevX[L - 1];
            int b = pdp[L - 1];
            if (a <= b) dpL[j][i] = 1;
        }
    }
    for (int j = k; j >= 1; j--)
    {
        vector<int> ndp(n + 1, n + 1);
        for (int i = n - 1; i >= 0; i--)
        {
            if (i + 1 < n) ndp[i] = ndp[i + 1];
            if (dpR[j + 1][i]) ndp[i] = i;
        }
        for (int i = n - 1; i >= 1; i--)
        {
            int R = i + c[j];
            if (R + 1 >= n + 1 || s[R] == 'X') continue;
            if (cnt_[R - 1] - cnt_[i - 1] != 0) continue;
            int a = nextX[R + 1];
            int b = ndp[R + 1];
            if (b <= a) dpR[j][i] = 1;
        }
    }

    // all below is O(nk)

    vector<int> canX(s.size()), can_(s.size());
    for (int j = 0; j < k + 2; j++)
    {
        for (int i = c[j] - 1; i < n; i++)
        {
            if (dpL[j][i] && dpR[j][i - c[j] + 1])
            {
                for (int p = i - c[j] + 1; p <= i; p++)
                {
                    canX[p] = 1;
                }
            }
            else
            {
                dpL[j][i] = 0;
                dpR[j][i - c[j] + 1] = 0;
            }
        }
    }
    for (int i = 1; i < s.size(); i++)
    {
        if (s[i] == 'X') continue;
        for (int j = 0; j < k + 2; j++)
        {
            if (dpL[j][i - 1]) dpL[j][i] = 1;
        }
    }
    for (int i = s.size() - 2; i >= 0; i--)
    {
        if (s[i] == 'X') continue;
        for (int j = 0; j < k + 2; j++)
        {
            if (dpR[j][i + 1]) dpR[j][i] = 1;
        }
    }
    for (int i = 1; i < s.size() - 1; i++)
    {
        for (int j = 0; j + 1 < k + 2; j++)
        {
            if (dpL[j][i - 1] && dpR[j + 1][i + 1]) can_[i] = 1;
        }
    }
    string ans = "";
    for (int i = 2; i < s.size() - 2; i++)
    {
        if (!canX[i] && !can_[i]) exit(222);
        if (s[i] != '.')
        {
            ans += s[i];
            continue;
        }
        if (canX[i] && can_[i]) ans += "?";
        if (!canX[i]) ans += "_";
        if (!can_[i]) ans += "X";
    }
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:31:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (int i = 1; i < s.size(); i++)
      |                     ~~^~~~~~~~~~
paint.cpp:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int i = 1; i < s.size(); i++)
      |                     ~~^~~~~~~~~~
paint.cpp:109:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for (int i = 1; i < s.size(); i++)
      |                     ~~^~~~~~~~~~
paint.cpp:125:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     for (int i = 1; i < s.size() - 1; i++)
      |                     ~~^~~~~~~~~~~~~~
paint.cpp:133:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |     for (int i = 2; i < s.size() - 2; i++)
      |                     ~~^~~~~~~~~~~~~~

• 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