Submission #593280

#	Time	Username	Problem	Language	Result	Execution time	Memory
593280		Soumya1	Paint By Numbers (IOI16_paint)	C++17	100 / 100	282 ms	43720 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#ifdef __LOCAL__
  #include <debug_local.h>
#endif
using namespace std;
const int mxN = 2e5 + 5;
const int mxK = 105;
bool pdp[mxK][mxN];
bool sdp[mxK][mxN];
int prefX[mxN], pref_[mxN];
string solve_puzzle(string s, vector<int> c) {
  int k = c.size();
  c.insert(c.begin(), 0);
  int n = s.size();
  s = '#' + s;
  s = s + '#';
  for (int i = 1; i <= n; i++) {
    prefX[i] = prefX[i - 1] + (s[i] == 'X');
    pref_[i] = pref_[i - 1] + (s[i] == '_');
  }
  pdp[0][0] = true;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= k; j++) {
      if (j == 0) {
        pdp[j][i] = true;
        if (s[i] == 'X') pdp[j][i] = false;
        pdp[j][i] &= pdp[j][i - 1];
        continue;
      }
      if (s[i] != 'X') {
        pdp[j][i] |= pdp[j][i - 1];
      }
      if (s[i] != '_') {
        if (i - c[j] == 0 && j != 1) continue;
        if (i - c[j] == 0) {
          if (pref_[i] - pref_[i - c[j]] > 0) continue;
          if (s[i + 1] == 'X') continue;
          pdp[j][i] = true;
          continue;
        }
        if (i - c[j] < 0 || pref_[i] - pref_[i - c[j]] > 0 || s[i - c[j]] == 'X' || s[i + 1] == 'X') continue;
        pdp[j][i] |= pdp[j - 1][i - c[j] - 1];
      }
    }
  }
  sdp[k + 1][n + 1] = true;
  for (int i = n; i >= 1; i--) {
    for (int j = k + 1; j >= 1; j--) {
      if (j == k + 1) {
        sdp[j][i] = true;
        if (s[i] == 'X') sdp[j][i] = false;
        sdp[j][i] &= sdp[j][i + 1];
        continue;
      }
      if (s[i] != 'X') {
        sdp[j][i] |= sdp[j][i + 1];
      }
      if (s[i] != '_') {
        if (i + c[j] == n + 1 && j != k) continue;
        if (i + c[j] == n + 1) {
          if (pref_[i + c[j] - 1] - pref_[i - 1] > 0) continue;
          if (s[i - 1] == 'X') continue;
          sdp[j][i] = true;
          continue;
        }
        if (i + c[j] > n + 1 || pref_[i + c[j] - 1] - pref_[i - 1] > 0 || s[i + c[j]] == 'X' || s[i - 1] == 'X') continue;
        sdp[j][i] |= sdp[j + 1][i + c[j] + 1];
      }
    }
  }
  bool off[n + 1], on[n + 1];
  memset(off, false, sizeof off);
  memset(on, false, sizeof on);
  for (int i = 1; i <= n; i++) {
    if (s[i] != '.') continue;
    for (int j = 0; j <= k; j++) {
      if (pdp[j][i - 1] && sdp[j + 1][i + 1]) off[i] = true;
    }
  }
  vector<int> add(n + 2);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= k; j++) {
      if (i - c[j] == 0 && j != 1) continue;
      if (i - c[j] == 0) {
        if (pref_[i] - pref_[i - c[j]] > 0) continue;
        if (i == n && j != k) continue;
        if (i < n && !sdp[j + 1][i + 2]) continue;
        if (s[i + 1] == 'X') continue;
        add[i]++;
        add[i - c[j]]--;
      }
      if (i - c[j] < 0 || pref_[i] - pref_[i - c[j]] > 0 || s[i - c[j]] == 'X') continue;
      if (!pdp[j - 1][i - c[j] - 1]) continue;
      if (i == n && j != k) continue;
      if (i < n && !sdp[j + 1][i + 2]) continue;
      if (s[i + 1] == 'X') continue;
      add[i]++;
      add[i - c[j]]--;
    }
  }
  for (int i = n; i >= 1; i--) {
    add[i] += add[i + 1];
    on[i] = add[i];
  }
  string ret;
  for (int i = 1; i <= n; i++) {
    if (s[i] == 'X') ret += s[i];
    if (s[i] == '_') ret += s[i];
    if (s[i] == '.') {
      if (off[i] && on[i]) ret += '?';
      else if (off[i]) ret += '_';
      else ret += 'X';
    }
  }
  return ret;
}

• 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