Submission #288700

#	Time	Username	Problem	Language	Result	Execution time	Memory
288700		IgorI	Paint By Numbers (IOI16_paint)	C++17	90 / 100	2096 ms	5496 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];

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();
    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++)
    {
        for (int i = 1; i < n; i++)
        {
            if (j == k)
            {
                int t = 1;
                for (int p = i + 1; p < n - 1; p++) if (s[p] == 'X') t = 0;
                if (!t) continue;
            }
            int L = i - c[j];
            if (L < 0 || s[L] == 'X') continue;
            int t = 1;
            for (int f = L + 1; f <= i; f++)
            {
                if (s[f] == '_')
                {
                    t = 0;
                    break;
                }
            }
            if (!t) continue;
            for (int f = L - 1; f >= 0; f--)
            {
                if (dpL[j - 1][f])
                {
                    dpL[j][i] = 1;
                    break;
                }
                if (s[f] == 'X') break;
            }
        }
    }
    for (int j = k; j >= 1; j--)
    {
        for (int i = n - 1; i >= 1; i--)
        {
            if (j == 1)
            {
                int t = 1;
                for (int p = i - 1; p > 0; p--) if (s[p] == 'X') t = 0;
                if (!t) continue;
            }
            int R = i + c[j];
            if (R >= n + 1 || s[R] == 'X') continue;
            int t = 1;
            for (int f = i; f < R; f++)
            {
                if (s[f] == '_')
                {
                    t = 0;
                    break;
                }
            }
            if (!t) continue;
            for (int f = R + 1; f < n; f++)
            {
                if (dpR[j + 1][f])
                {
                    dpR[j][i] = 1;
                    break;
                }
                if (s[f] == 'X') break;
            }
        }
    }

    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:119:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |     for (int i = 1; i < s.size(); i++)
      |                     ~~^~~~~~~~~~
paint.cpp:135:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     for (int i = 1; i < s.size() - 1; i++)
      |                     ~~^~~~~~~~~~~~~~
paint.cpp:143:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |     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: 0 / 10