제출 #94573

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
94573		wxh010910	Paint By Numbers (IOI16_paint)	C++17	100 / 100	344 ms	31136 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"

using namespace std;

string solve_puzzle(string s, vector<int> c) {
  int n = s.size(), m = c.size();
  vector<int> sum(n + 1);
  for (int i = 0; i < n; ++i) {
    sum[i + 1] = sum[i] + (s[i] == '_');
  }
  vector<int> black(n + 1);
  vector<vector<bool>> l(n + 1, vector<bool>(m + 1));
  l[0][0] = true;
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j <= m; ++j) {
      if (s[i - 1] != 'X' && l[i - 1][j]) {
        l[i][j] = true;
      } else if (j && i >= c[j - 1] && sum[i] == sum[i - c[j - 1]]) {
        if (j == 1) {
          l[i][j] = l[i - c[j - 1]][j - 1];
        } else if (i > c[j - 1]) {
          l[i][j] = l[i - c[j - 1] - 1][j - 1] && s[i - c[j - 1] - 1] != 'X';
        }
      }
    }
  }
  vector<vector<bool>> r(n + 1, vector<bool>(m + 1));
  r[n][m] = true;
  for (int i = n - 1; ~i; --i) {
    for (int j = m; ~j; --j) {
      if (j < m && i <= n - c[j] && sum[i] == sum[i + c[j]]) {
        if (j == m - 1) {
          r[i][j] = r[i + c[j]][j + 1];
        } else if (i < n - c[j]) {
          r[i][j] = r[i + c[j] + 1][j + 1] && s[i + c[j]] != 'X';
        }
        if (r[i][j]) {
          bool ok = false;
          if (!j) {
            ok = l[i][j];
          } else if (i) {
            ok = l[i - 1][j] && s[i - 1] != 'X';
          }
          if (ok) {
            ++black[i];
            --black[i + c[j]];
          }
        }
      }
      if (s[i] != 'X' && r[i + 1][j]) {
        r[i][j] = true;
      }
    }
  }
  string ans = s;
  for (int i = 0; i < n; ++i) {
    black[i + 1] += black[i];
    if (s[i] == '.') {
      if (black[i]) {
        bool white = false;
        for (int j = 0; j <= m; ++j) {
          if (l[i][j] && r[i + 1][j]) {
            white = true;
            break;
          }
        }
        if (white) {
          ans[i] = '?';
        } else {
          ans[i] = 'X';
        }
      } else {
        ans[i] = '_';
      }
    }
  }
  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