제출 #296770

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
296770		Haunted_Cpp	Paint By Numbers (IOI16_paint)	C++17	10 / 100	293 ms	333812 KiB

paint

#include "paint.h"

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

const int MAX_N = 2e5 + 5;
const int MAX_K = 1e2 + 5;

int dp[MAX_N][MAX_K][2];
bitset<2> vis[MAX_N][MAX_K];

vector<int> white, black;

vector<int> c;
string s;

int n, K;

int range_sum(int lo, int hi) {
  return white[hi] - (lo - 1 >= 0 ? white[lo - 1] : 0);
}

int solve(int p, int k, bool can) {
  if (p >= n) return dp[p][k][can] = (k == K);
  int &res = dp[p][k][can];
  if (~res) return res;
  res = 0;
  if (s[p] == '_' || s[p] == '.') {
    res = max(res, solve(p + 1, k, true));
  }  
  if (k < K && can && (s[p] == 'X' || s[p] == '.')) {
    const int t = c[k];
    if (p + t > n) return res;
    const int cur = range_sum(p, p + t - 1);
    if (cur == 0) {
      res = max(res, solve(p + t, k + 1, false));
    }
  }
  return res;
}

vector<int> W, B;


void backtrack(int p, int k, int can) {
  if (p >= n) {
    return;
  }
  if (vis[p][k][can]) {
    return;
  }
  vis[p][k][can] = 1;
  int white_works = 0;
  if (s[p] == '_' || s[p] == '.') {
    white_works = solve(p + 1, k, true);
  }
  int black_works = 0;
   if (k < K && can && (s[p] == 'X' || s[p] == '.')) {
    const int t = c[k];
    if (p + t <= n) {
      const int cur = range_sum(p, p + t - 1);
      if (cur == 0) {
        black_works = solve(p + t, k + 1, false);
      }
      if (black_works) {
        ++B[p];
        --B[p + t];
        //~ cout << "ADD:" << p << ' ' << p + t << '\n';
        backtrack(p + t, k + 1, false);
      }
    }
  }
  //~ assert(white_works || black_works);
  if (white_works) {
    //~ cout << p << ' ';
    W[p] = 1;
    backtrack(p + 1, k, true);
  }
}

string solve_puzzle(string s, vector<int> c) {
  ::c = c;
  ::s = s;
  n = s.size();
  K = c.size();
  memset(dp, -1, sizeof(dp));
  white = black = vector<int>(n);
  auto work = [&](vector<int>& arr, const char t) {
    arr[0] = (s[0] == t);
    for (int i = 1; i < n; i++) {
      arr[i] = arr[i - 1] + (s[i] == t);
    }
  };
  work(white, '_');
  work(black, 'X');
  solve(0, 0, true);
  W = B = vector<int>(n);
  backtrack(0, 0, true);
  string res = string(n, 'z');
  int cur = 0;
  for (int i = 0; i < n; i++) {
    cur += B[i];
    if (cur > 0 && W[i] > 0) {
      res[i] = '?';
      continue;
    }
    if (cur > 0) {
      res[i] = 'X';
      continue;
    }
    if (W[i] > 0) {
      res[i] = '_';
      continue;
    }
    //~ assert(1 == 2);
  }
  return res;
}

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 0 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10