Submission #296780

#	Time	Username	Problem	Language	Result	Execution time	Memory
296780		Haunted_Cpp	Paint By Numbers (IOI16_paint)	C++17	10 / 100	3 ms	768 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<vector<vector<int>>> dp, vis;

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();
  dp = vector<vector<vector<int>>> (n + 5, vector<vector<int>>(min(n, K) + 5, vector<int>(2, -1)));
  vis = vector<vector<vector<int>>> (n + 5, vector<vector<int>>(min(n, K) + 5, vector<int>(2, 0)));
  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