제출 #471740

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
471740		flashmt	Paint By Numbers (IOI16_paint)	C++17	59 / 100	1 ms	332 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 + 1));
  for (int i = 1; i <= n; 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] = ff[i][j - 1] | f[i][j];
    for (int j = c[i]; j <= n; j++)
    {
      if (a[0][j] != a[0][j - c[i]])
        continue;
      if (j > c[i] && s[j - c[i]] == 'X')
        continue;
      if (j < n && s[j + 1] == 'X')
        continue;
      if (!i) f[1][j] = !a[1][j - c[i]];
      else if (j > c[i]) f[i + 1][j] = ff[i][j - c[i] - 1];
    }

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

  vector<int> maxG(k + 1);
  maxG[0] = n + 1;
  for (int i = 1; i <= k; i++)
    for (int j = n; j; j--)
      if (g[i][j])
      {
        maxG[i] = j;
        break;
      }

  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++)
    for (int j = 1; j <= n; j++)
      if (f[i][j])
      {
        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
        {
          int jj = min(rx[j + 1] - 1, maxG[k - i]);
          if (jj <= j + 1)
            continue;
          update(1, j - c[i - 1] + 1, j);
          update(0, j + 1, jj - 1);
        }

        if (i == 1)
        {
          int jj = min(rx[j + 1] - 1, maxG[k - i]);
          if (k > 1 && jj <= j + 1)
            continue;
          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;
}

• 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