Submission #23677

#	Time	Username	Problem	Language	Result	Execution time	Memory
23677		Nirjhor	Paint By Numbers (IOI16_paint)	C++14	90 / 100	2000 ms	100120 KiB

paint

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

using namespace std;

const int K = 105;
const int N = 200010;

string s;
vector <int> c;
int x[N], u[N];
int n, k, tot[N];
int dp[N][K];

int u_in_range (int l, int r) {
  return tot[r] - (l > 0 ? tot[l - 1] : 0);
}

void update_x (int l, int r) {
  ++x[l], --x[r + 1];
}

void update_u (int l, int r) {
  ++u[l], --u[r + 1];
}

int call (int at, int block) {
  if (at >= n) return block == k;
  if (block == k) {
    if (s[at] == '_') {
      int ret = call(at + 1, block);
      if (ret) update_u(at, at);
      return ret;
    } else if (s[at] == '.') {
      int ret = call(at + 1, block);
      if (ret) update_u(at, at);
      return ret;
    } else {
      return 0;
    }
  }
  int &ret = dp[at][block];
  if (ret != -1) return ret;
  if (s[at] == '_') {
    ret = call(at + 1, block);
    if (ret) update_u(at, at);
    return ret;
  } 
  if (s[at] == 'X') {
    int nxt = at + c[block];
    if (nxt > n) return ret = 0;
    if (u_in_range(at, nxt - 1) > 0) {
      return ret = 0;
    } 
    if (nxt < n and s[nxt] == 'X') {
      return ret = 0;
    }
    ret = call(nxt + 1, block + 1);
    if (ret) {
      if (nxt < n) {
        update_u(nxt, nxt);
      }
      update_x(at, nxt - 1);
    }
    return ret;
  } 
  int one = call(at + 1, block);
  // cout << at << " " << block << " " << one <<  endl;
  if (one) update_u(at, at); 
  int two, nxt = at + c[block];
  if (nxt > n) two = 0;
  else if (u_in_range(at, nxt - 1) > 0) {
    two = 0;
  } else if (nxt < n and s[nxt] == 'X') {
    two = 0;
  } else { 
    two = call(nxt + 1, block + 1);
    if (two) {
      if (nxt < n) {
        update_u(nxt, nxt);
      }
      update_x(at, nxt - 1);
    }
  }
  return ret = one | two;
}

string solve_puzzle (string s_in, vector <int> c_in) {
  s = s_in, c = c_in;
  n = s.size(), k = c.size();
  memset(dp, -1, sizeof dp);
  for (int i = 0; i < n; ++i) {
    if (i > 0) tot[i] = tot[i - 1];
    if (s[i] == '_') {
      ++tot[i];
    }
  }
  // cout << call(5, 1) << endl;
  call(0, 0);
  string res = "";
  for (int i = 0; i < n; ++i) {
    if (i) {
      x[i] += x[i - 1];
      u[i] += u[i - 1];
    }
    // cout << i << " " << x[i] << " " << u[i] << endl;
    if (x[i] and u[i]) res += '?';
    else if (x[i]) res += 'X';
    else res += '_';  
  }
  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