Submission #200896

#	Time	Username	Problem	Language	Result	Execution time	Memory
200896		oofsauce	Paint By Numbers (IOI16_paint)	C++14	90 / 100	2074 ms	14328 KiB

paint

#include "paint.h"

#include <cstdlib>
#include <bits/stdc++.h>

using namespace std;

string s;
vector<int> c;
int n;
int k;

vector<bool> defB;
vector<bool> mayB;
vector<bool> defW;
vector<bool> mayW;

vector<vector<bool>> visited;
vector<vector<bool>> valid;

bool solve(int clueIdx, int strIdx) {
  if(strIdx >= n) return clueIdx == k;
  if(clueIdx == k) {
    for(int i = strIdx; i < n; i++)
      if(s[i] == 'X') return false;
    for(int i = strIdx; i < n; i++)
      mayW[i] = true;
    return true;
  }
  if(visited[clueIdx][strIdx]) return valid[clueIdx][strIdx];
  visited[clueIdx][strIdx] = true;
  bool dontpick = s[strIdx] != 'X' && solve(clueIdx, strIdx + 1);
  // cout << dontpick << endl;
  if(dontpick) mayW[strIdx] = true;
  for(int i = 0; i < c[clueIdx]; i++) {
    if(strIdx+i >= n || s[strIdx+i] == '_') return valid[clueIdx][strIdx] = dontpick;
  }
  if(strIdx+c[clueIdx] < n && s[strIdx+c[clueIdx]] == 'X') return valid[clueIdx][strIdx] = dontpick;
  bool pick = solve(clueIdx + 1, strIdx+c[clueIdx]+1);
  // cout << pick << endl<<endl;
  if(pick) {
    for(int i = 0; i < c[clueIdx]; i++)
      mayB[strIdx + i] = true;
    if(strIdx+c[clueIdx] < n)
      mayW[strIdx+c[clueIdx]] = true;
  }
  return valid[clueIdx][strIdx] = pick || dontpick;
}

string solve_puzzle(string s_, vector<int> c_) {
  s = s_;
  c = c_;

  n = s.size();
  k = c.size();

  defB.resize(n, false);
  mayB.resize(n, false);
  defW.resize(n, false);
  mayW.resize(n, false);
  visited.resize(k, vector<bool>(n));
  valid.resize(k, vector<bool>(n));

  string ans = "";

  solve(0,0);
  // for(int i = 0; i < n; i++) cout << mayB[i] << " "; cout << endl;
  // for(int i = 0; i < n; i++) cout << mayW[i] << " "; cout << endl;
  for(int i = 0; i < n; i++) {
    if     (mayB[i] && mayW[i]) ans += "?";
    else if(mayB[i] && !mayW[i]) ans += "X";
    else if(!mayB[i] && mayW[i]) ans += "_";
    else if(!mayB[i] && !mayW[i]) 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