Submission #296790

#	Time	Username	Problem	Language	Result	Execution time	Memory
296790		Haunted_Cpp	Paint By Numbers (IOI16_paint)	C++17	90 / 100	2108 ms	511924 KiB

paint

#include "paint.h"

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

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

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

vector<int> white, c, B;


bitset<MAX_N> W;
//~ vector<int> B;


//~ 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);
  if (calc[p][k][can]) return dp[p][k][can];
  calc[p][k][can] = true;
  int 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 dp[p][k][can] = res;
}


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[min(n, p + t)];
        backtrack(p + t, 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] == '_');
  }
  //~ solve(0, 0, true);
  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;
    }
    //~ assert(1 == 2);
  }
  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: 0 / 10