Submission #257877

#	Time	Username	Problem	Language	Result	Execution time	Memory
257877		ipaljak	Paint By Numbers (IOI16_paint)	C++14	100 / 100	1040 ms	86020 KiB

paint

#include "paint.h"

#include <cassert>
#include <cstdlib>
#include <iostream>

using namespace std;

const int MAXN = 2e5 + 5;
const int MAXK = 105;

int n, k;
int pb[MAXN], pw[MAXN];

bool dp_pref[MAXN][MAXK][2], dp_suff[MAXN][MAXK][2];
int bcnt[MAXN];

int sum(int *pref, int lo, int hi) { return pref[hi] - pref[lo - 1]; }

string solve_puzzle(string s, vector<int> c) {
  n = (int)s.size();
  k = (int)c.size();

  for (int i = 0; i < (int)s.size(); ++i) {
    pb[i + 1] = pb[i] + (s[i] == 'X');
    pw[i + 1] = pw[i] + (s[i] == '_');
  }

  dp_pref[0][0][0] = dp_pref[0][0][1] = true;
  for (int i = 1; i <= n && s[i - 1] != 'X'; ++i)
    dp_pref[i][0][0] = dp_pref[i][0][1] = true;

  dp_suff[n + 1][k + 1][0] = dp_suff[n + 1][k + 1][1] = true;
  for (int i = n; i >= 1 && s[i - 1] != 'X'; --i)
    dp_suff[i][k + 1][0] = dp_suff[i][k + 1][1] = true;

  for (int j = 1; j <= k; ++j) {
    for (int i = 1; i <= n; ++i) {
      if (s[i - 1] != 'X')
        dp_pref[i][j][0] |= dp_pref[i - 1][j][0] | dp_pref[i - 1][j][1];
      dp_pref[i][j][1] |= i >= c[j - 1] && sum(pw, i - c[j - 1] + 1, i) == 0 &&
                          dp_pref[i - c[j - 1]][j - 1][0];
    }
  }

  for (int j = k; j >= 1; --j) {
    for (int i = n; i >= 1; --i) {
      if (s[i - 1] != 'X')
        dp_suff[i][j][0] |= dp_suff[i + 1][j][0] | dp_suff[i + 1][j][1];
      dp_suff[i][j][1] |= i + c[j - 1] - 1 <= n &&
                          sum(pw, i, i + c[j - 1] - 1) == 0 &&
                          dp_suff[i + c[j - 1]][j + 1][0];
    }
  }

  assert(dp_pref[n][k][0] || dp_pref[n][k][1]);
  assert(dp_suff[1][1][0] || dp_suff[1][1][1]);

  for (int i = 0; i < n; ++i) {
    for (int j = 1; j <= k; ++j) {
      if (dp_pref[i + 1][j][1] && dp_suff[i + 2][j + 1][0]) {
        bcnt[i - c[j - 1] + 1]++;
        bcnt[i + 1]--;
      }
    }
  }

  string ret = "";
  int bsum = 0;
  for (int i = 0; i < n; ++i) {
    bsum += bcnt[i];
    if (s[i] != '.') {
      ret.push_back(s[i]);
      continue;
    }
    bool black = bsum > 0, white = false;
    for (int j = 0; j <= k; ++j) {
      white |=
          (dp_pref[i + 1][j][0] &&
           (dp_suff[i + 2][j + 1][0] || dp_suff[i + 2][j + 1][1])) ||
          ((dp_pref[i][j][0] || dp_pref[i][j][1]) && dp_suff[i + 1][j + 1][0]);
    }
    assert(black || white);
    if (black && !white) {
      ret.push_back('X');
      continue;
    }
    if (!black && white) {
      ret.push_back('_');
      continue;
    }
    ret.push_back('?');
  }

  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