Submission #471751

#	Time	Username	Problem	Language	Result	Execution time	Memory
471751		flashmt	Paint By Numbers (IOI16_paint)	C++17	100 / 100	824 ms	323656 KiB

paint

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

string solve_puzzle(string s, vector<int> c)
{
  int n = size(s), k = size(c);
  s = " " + s + " ";
  vector<vector<int>> a(2, vector<int>(n + 2));
  for (int i = 1; i <= n + 1; i++)
  {
    a[0][i] = a[0][i - 1] + (s[i] == '_');
    a[1][i] = a[1][i - 1] + (s[i] == 'X');
  }

  vector<vector<int>> f(k + 1, vector<int>(n + 2)), g, ff, gg;
  g = ff = gg = f;
  ff[0][0] = gg[0][n + 1] = 1;
  for (int i = 0; i < k; i++)
  {
    for (int j = 1; j <= n; j++)
      ff[i][j] = f[i][j] | (ff[i][j - 1] & (s[j] != 'X'));
    for (int j = c[i]; j <= n; j++)
    {
      int jj = j - c[i];
      if (a[0][j] != a[0][jj])
        continue;
      if (jj && s[jj] == 'X')
        continue;
      if (j < n && s[j + 1] == 'X')
        continue;
      if (!i) f[1][j] = !a[1][jj];
      else if (jj) f[i + 1][j] = ff[i][jj - 1];
    }

    for (int j = n; j; j--)
      gg[i][j] = g[i][j] | (gg[i][j + 1] & (s[j] != 'X'));
    for (int j = n + 1 - c[k - 1 - i]; j; j--)
    {
      int jj = j + c[k - 1 - i] - 1;
      if (a[0][jj] != a[0][j - 1])
        continue;
      if (jj < n && s[jj + 1] == 'X')
        continue;
      if (j && s[j - 1] == 'X')
        continue;
      if (!i) g[1][j] = jj == n || a[1][n] == a[1][jj];
      else if (jj < n) g[i + 1][j] = gg[i][jj + 2];
    }
  }

  vector<int> rx(n + 2, n + 1);
  for (int i = n; i; i--)
    if (s[i] == 'X') rx[i] = i;
    else rx[i] = rx[i + 1];

  vector<vector<int>> can(2, vector<int>(n + 2));
  auto update = [&](int v, int l, int r)
  {
    can[v][l]++;
    can[v][r + 1]--;
  };

  for (int i = 1; i <= k; i++)
  {
    vector<int> idG;
    for (int j = n; j; j--)
      if (g[k - i][j])
        idG.push_back(j);

    for (int j = 1; j <= n; j++)
      if (f[i][j])
      {
        int bound = rx[j + 1];
        while (size(idG) >= 2 && idG[size(idG) - 2] <= bound)
          idG.pop_back();

        if (i == k)
        {
          if (a[1][n] != a[1][j])
            continue;
          update(1, j - c[i - 1] + 1, j);
          update(0, j + 1, n);
        }
        else if (!empty(idG) && idG.back() > j + 1 && idG.back() <= bound)
        {
          update(1, j - c[i - 1] + 1, j);
          update(0, j + 1, idG.back() - 1);
        }

        if (i == 1)
          if (k == 1 || !empty(idG) && idG.back() > j + 1 && idG.back() <= bound)
            update(0, 1, j - c[i - 1]);
      }
  }

  string ans;
  for (int i = 1; i <= n; i++)
  {
    can[0][i] += can[0][i - 1];
    can[1][i] += can[1][i - 1];
    if (can[0][i] && can[1][i]) ans += '?';
    else if (can[0][i]) ans += '_';
    else ans += 'X';
  }

  return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:91:59: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   91 |           if (k == 1 || !empty(idG) && idG.back() > j + 1 && idG.back() <= bound)
      |                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• 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