Submission #21881

#	Time	Username	Problem	Language	Result	Execution time	Memory
21881		sampriti	Paint By Numbers (IOI16_paint)	C++14	100 / 100	623 ms	175032 KiB

paint

#include "paint.h"

#include <cstring>
#include <string>
#include <cstdlib>
#include <cassert>
#include <string>
#include <vector>

using namespace std;

string S;
vector<int> A;
int N, K;
int dp[2][101][200000];  // dp[k][j][i] = is it possible to have valid string for i...N with clues j...K and current character (k=0|black or 1|white)
int pref[2][200000];

inline int get_sum(int i, int L, int R) {
  if(L == 0) return pref[i][R];
  return pref[i][R] - pref[i][L - 1];
}

int solve(int i, int j, int k) {
  if(i == N) return (j == K);
  if(dp[k][j][i] != -1) return dp[k][j][i];

  int ans = 0;
  if(k == 0) {
    if(S[i] != '_' && j < K) {
      if(get_sum(1, i, i + A[j] - 1) == 0 && i + A[j] <= N) {
        ans = solve(i + A[j], j + 1, 1);
      }
    }
  }
  else {
    if(S[i] != 'X') ans = solve(i + 1, j, 0) | solve(i + 1, j, 1);
  }
  return dp[k][j][i] = ans;
}

string solve_puzzle(string _S, vector<int> _A) {
  S = _S;
  A = _A;
  N = S.length();
  K = A.size();

  memset(pref, 0, sizeof pref);
  if(S[0] == 'X') pref[0][0]++;
  else if(S[0] == '_') pref[0][1]++;
  for(int i = 1; i < N; i++) {
    pref[0][i] = pref[0][i - 1];
    pref[1][i] = pref[1][i - 1];
    if(S[i] == 'X') pref[0][i]++;
    else if(S[i] == '_') pref[1][i]++;
  }

  memset(dp, -1, sizeof dp);
  solve(0, 0, 0);
  solve(0, 0, 1);

  string ans = "";
  int ptr = -1;
  for(int i = 0; i < N; i++) {
    bool white_pos = false;
    for(int j = 0; j <= K; j++) {
      if(dp[0][j][i] == 1) ptr = max(ptr, i + A[j] - 1);
      if(dp[1][j][i] == 1) white_pos = true;
    }
    bool black_pos = (i <= ptr);
    if(black_pos && white_pos) ans += '?';
    else if(black_pos) ans += 'X';
    else if(white_pos) ans += '_';
    else assert(false);
  }
  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