Submission #1081058

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081058		erray	Paint By Numbers (IOI16_paint)	C++17	59 / 100	1 ms	348 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG 
  #include "/home/ioi/contests/ioi16d2/debug.h"
#else 
  #define debug(...) void(37)
#endif

std::string solve_puzzle(std::string S, std::vector<int> c) {
  debug(S);
  int N = int(S.size());
  int K = int(c.size());
  vector<int> pref(N + 1);
  for (int i = 0; i < N; ++i) {
    pref[i + 1] = pref[i] + (S[i] == '_');
  }
  vector<vector<bool>> norm(N + 2, vector<bool>(K + 1, false));
  auto rev = norm;
  {
    norm[0][0] = true;
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j <= K; ++j) {
        if (!norm[i][j]) continue;
        if (S[i] != 'X') norm[i + 1][j] = true;
        int s = (j == K ? N + 1 : c[j]);
        if (j < K && i + s <= N && pref[i + s] - pref[i] == 0) {
          int to = i + s + 1;
          norm[to][j + 1] = true;
        }
      }
    }
  }
  debug(norm);
  {
    rev[N][K] = true;
    for (int i = N - 1; i >= 0; --i) {
      for (int j = 0; j <= K; ++j) {
        if (!rev[i + 1][j]) continue;
        if (S[i] != 'X') rev[i][j] = true;
        int s = (j == 0 ? N + 1 : c[j - 1]);
        if (j > 0 && i >= s && pref[i + 1] - pref[i + 1 - s] == 0) {
          //int to = max(0, i - s);
          rev[i - s][j - 1] = true;
        }
      }
    }
  }
  debug(rev);
  vector<int> sums(N + 1);
  for (int j = 0; j < K; ++j) {
    int s = c[j];
    for (int i = 0; i + s <= N; ++i) {
      if (norm[i][j] && rev[i + s][j + 1] && pref[i + s] - pref[i] == 0) {
        sums[i + s] -= 1;
        sums[i] += 1;
      }
    }
  }
  for (int i = 0; i < N; ++i) {
    sums[i + 1] += sums[i];
  }
  string res(N, '*');
  for (int i = 0; i < N; ++i) {
    bool black = sums[i] > 0;
    bool white = false;
    for (int j = 0; j <= K; ++j) {
      if (S[i] != 'X' && norm[i + 1][j] && rev[i][j]) {
        white = true;
      }
    }
    if (black && white) {
      res[i] = '?';
    } else if (black) {
      res[i] = 'X';
    } else if (white) {
      res[i] = '_';
    } else {
      assert(false);
    }
  }
  return res;
}

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10