Submission #575827

#	Time	Username	Problem	Language	Result	Execution time	Memory
575827		lorenzoferrari	Paint By Numbers (IOI16_paint)	C++17	100 / 100	1037 ms	144012 KiB

paint

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

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

  vector<int> cnt_(n+1);
  for (int i = 0; i < n; ++i) {
    cnt_[i+1] = cnt_[i] + (s[i] == '_');
  }

  auto anywhite = [&](int l, int r) -> bool {
    l = max(l, 0);
    return cnt_[r+1] - cnt_[l] > 0;
  };

  vector<vector<bool>> white(n, vector<bool>(k+1, false));
  vector<vector<bool>> black(n, vector<bool>(k+1, false));
  // white[n][k]: può essere white e avere k blocchi completati?
  // black[n][k]: può essere black e la fine del k-esimo blocco?
  for (int i = 0; i < n; ++i) white[i][0] = (s[i] != 'X' && (!i || white[i-1][0]));
  for (int j = 1; j <= k; ++j) {
    white[0][j] = false;
    black[0][j] = (s[0] != '_' && j == 1 && c[0] == 1);
    for (int i = 1; i < n; ++i) {
      white[i][j] = (s[i] != 'X') && (white[i-1][j] || black[i-1][j]);
      if (j == 1) {
        black[i][j] = !anywhite(i-c[j-1]+1, i) && (i+1 >= c[j-1] && (i+1 == c[j-1] || white[i-c[j-1]][j-1]));
      } else {
        black[i][j] = !anywhite(i-c[j-1]+1, i) && (i >= c[j-1] && white[i-c[j-1]][j-1]);
      }
    }
  }

  return make_pair(white, black);
}

string solve_puzzle(string s, vector<int> c) {
  int n = s.size();
  int k = c.size();
  auto [white, black] = get_white_black(s, c);

  auto ss = s; reverse(ss.begin(), ss.end());
  auto cc = c; reverse(cc.begin(), cc.end());
  auto [rwhite, rblack] = get_white_black(ss, cc);

  auto rev = [&](int i) -> int { return n - 1 - i; };

  for (int j = 0; j < k; ++j) {
    white[n-1][j] = black[n-1][j] = false;
  }
  for (int j = 0; j <= k; ++j) {
    for (int i = 0; i < n-1; ++i) {
      white[i][j] = white[i][j] && (rwhite[rev(i+1)][k-j] || rblack[rev(i+1)][k-j]);
      black[i][j] = black[i][j] &&  rwhite[rev(i+1)][k-j];
    }
  }

  vector<vector<int>> pblack(n+1, vector<int>(k+1));
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= k; ++j) {
      pblack[i+1][j] = pblack[i][j] + black[i][j];
    }
  }

  auto anyblack = [&](int l, int r, int j) -> bool {
    r = min(r, n-1);
    return (pblack[r+1][j] - pblack[l][j]) > 0;
  };

  // ans:
  // i can be _ if white[i][j] for any j
  // i can be X if black[i][j] for any j for any i \in [i, i+c[j-1]]

  vector<bool> ww(n, false);
  vector<bool> bb(n, false);
  string ans(n, '*');
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= k; ++j) ww[i] = ww[i] || white[i][j];
    for (int j = 1; j <= k; ++j) {
      bb[i] = bb[i] || anyblack(i, i+c[j-1]-1, j);
    }
    if (ww[i] && bb[i]) ans[i] = '?';
    else if (ww[i]) ans[i] = '_';
    else if (bb[i]) ans[i] = 'X';
    else ans[i] = '*';
  }
  return ans;
}

• 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