Submission #20612

#	Time	Username	Problem	Language	Result	Execution time	Memory
20612		model_code	Paint By Numbers (IOI16_paint)	C++11	90 / 100	2000 ms	29180 KiB

paint

// name = paint_mark_gordon_n2.cpp, type = cpp.g++

#include "paint.h"
#include <iostream>
#include <cstdlib>
#include <vector>
#include <cstdio>
 
using namespace std;
 
string solve_puzzle(string S, vector<int> C) {
  int M = C.size();
  int N = S.size();
 
  vector<bool> isb(N + 1, false);
  vector<int> cntb(N + 1, 0);
  for (int i = 0; i < N; i++) {
    if (S[i] == 'X') {
      isb[i] = true;
      cntb[i + 1] = 1;
    }
  }
 
  vector<bool> isw(N + 1, false);
  vector<int> cntw(N + 1, 0);
  for (int i = 0; i < N; i++) {
    if (S[i] == '_') {
      isw[i] = true;
      cntw[i + 1] = 1;
    }
  }
 
  for (int i = 1; i <= N; i++) {
    cntb[i] += cntb[i - 1];
    cntw[i] += cntw[i - 1];
  }
 
  vector<vector<bool> > DP_F(N + 1, vector<bool>(M + 1));
 
  DP_F[N][M] = true;
  for (int i = N - 1; i >= 0; i--) {
    for (int j = 0; j <= M; j++) {
      if (!isb[i]) {
        DP_F[i][j] = DP_F[i + 1][j];
      }
      if (j < M && i + C[j] <= N && DP_F[min(N, i + C[j] + 1)][j + 1] &&
            (i + C[j] == N || !isb[i + C[j]]) &&
            cntw[i] == cntw[i + C[j]]) {
        DP_F[i][j] = true;
      }
    }
  }
 
  vector<vector<bool> > DP_R(N + 1, vector<bool>(M + 1));
 
  DP_R[0][0] = true;
  for (int i = 1; i <= N; i++) {
    for (int j = M; j >= 0; j--) {
      if (!isb[i - 1]) {
        DP_R[i][j] = DP_R[i - 1][j];
      }
      if (j > 0 && i - C[j - 1] >= 0 && DP_R[max(0, i - C[j - 1] - 1)][j - 1] &&
            (i - C[j - 1] == 0 || !isb[i - C[j - 1] - 1]) &&
            cntw[i] == cntw[i - C[j - 1]]) {
        DP_R[i][j] = true;
      }
    }
  }
 
  S = "";
  for (int i = 0; i < N; i++) {
    bool canw = false;
    for (int j = 0; j <= M; j++) {
      canw |= !isb[i] && DP_R[i][j] && DP_F[i + 1][j];
    }
     
    bool canb = false;
    for (int j = 0; j < M; j++) {
      for (int k = 0; k < C[j]; k++) {
        if (0 <= i - k && i + C[j] - k <= N) {
          canb |= cntw[i - k] == cntw[i + C[j] - k] &&
                (i - k == 0 || !isb[i - k - 1]) &&
                (i + C[j] - k == N || !isb[i + C[j] - k]) &&
                DP_R[max(0, i - k - 1)][j] &&
                DP_F[min(N, i + C[j] - k + 1)][j + 1];
        }
      }
    }
 
    if (canw && canb) {
      S += '?';
    } else if (canw) {
      S += '_';
    } else if (canb) {
      S += 'X';
    } else {
      S += '*';
    }
  }
 
    return S;
}

• 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: 0 / 10