Submission #296807

#	Time	Username	Problem	Language	Result	Execution time	Memory
296807		Haunted_Cpp	Paint By Numbers (IOI16_paint)	C++17	100 / 100	1605 ms	33460 KiB

paint

#include "paint.h"

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

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

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

vector<int> white, c, B;

bitset<MAX_N> W;
string s;

int n, K;

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

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


void backtrack(int p, int k, int can) {
  if (p >= n) {
    return;
  }
  if (vis[k][can][p]) {
    return;
  }
  vis[k][can][p] = 1;
  int white_works = 0;
  if (s[p] == '_' || s[p] == '.') {
    white_works = solve(p + 1, k, true);
  }
  int black_works = 0;
   if (k < K && p + c[k] <= n && can && (s[p] == 'X' || s[p] == '.')) {
    //~ const int t = c[k];
    //~ if (p + t <= n) {
      const int cur = range_sum(p, p + c[k] - 1);
      if (cur == 0) {
        black_works = solve(min(n, p + c[k]), k + 1, false);
      }
      if (black_works) {
        ++B[p];
        --B[min(n, p + c[k])];
        backtrack(min(n, p + c[k]), k + 1, false);
      }
    //~ }
  }
  if (white_works) {
    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();
  white = vector<int>(n);
  white[0] = (s[0] == '_');
  for (int i = 1; i < n; i++) {
    white[i] = white[i - 1] + (s[i] == '_');
  }
  B = vector<int>(n + 5);
  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;
    }
  }
  return res;
}

• 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