Submission #120305

#	Time	Username	Problem	Language	Result	Execution time	Memory
120305		turbat	Paint By Numbers (IOI16_paint)	C++14	90 / 100	342 ms	334000 KiB

paint

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

int n, k, cnt[N], can[N], dp[N][205], paint[N];
vector <int> c;
string s, ans;

bool solve(int idx, int col){
  if (!col && !idx) return 1;
  if (idx < 0) return 0;
  if (dp[idx][col] != -1) return dp[idx][col];
  dp[idx][col] = 0;
  // cout << idx << ' '<< col << endl;
  if (s[idx] != 'X' && solve(idx - 1, col)) can[idx] = dp[idx][col] = 1;
  if (col && cnt[idx] - cnt[idx - c[col - 1]] == 0 && s[idx - c[col - 1]] != 'X')
    if ((col == 1 && !(idx - c[col - 1])) || solve(idx - c[col - 1] - 1, col - 1)){
      dp[idx][col] = 1;
      paint[idx]++;
      paint[idx - c[col - 1]]--;
      can[idx - c[col - 1]] = 1;
    }
  // cout << idx << ' '<< col << ' '<< dp[idx][col]<< endl;
  return dp[idx][col];
}
string solve_puzzle(string ss, vector<int> cc) {
  s = '_' + ss;
  c = cc;
  n = s.size();
  k = c.size();
  for (int i = 1;i < n;i++){
    if (s[i] == '_') cnt[i]++;
    cnt[i] += cnt[i - 1];
  }
  memset(dp, -1, sizeof dp);
  solve(n - 1, k);
  for (int i = n - 1;i > 0;i--) paint[i] += paint[i + 1];
  for (int i = 1;i < n;i++){
    int d = 0;
    if (paint[i]) d += 1;
    if (can[i]) d += 2;
    if (!d) ans += 'G';
    if (d == 1) ans += 'X';
    if (d == 2) ans += '_';
    if (d == 3) ans += '?';
  }
  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: 0 / 10