Submission #295892

#	Time	Username	Problem	Language	Result	Execution time	Memory
295892		erd1	Paint By Numbers (IOI16_paint)	C++14	90 / 100	323 ms	13560 KiB

paint

#include "paint.h"

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

const int N = 5000 + 2;


bitset<N> targB, targW;
vector<vector<bitset<N>>> dpB, dpW;
vector<vector<bool>> valid;

string solve_puzzle(string s, vector<int> c) {
  int k = c.size(), n = s.size();
  if(n > N)return "";
  for(int i = 0; i < n; i++)targB[i+2] = s[i] == 'X', targW[i+2] = s[i] == '_';
  dpB.resize(n+2); dpW.resize(n+2); valid.resize(n+2);
  for(auto& i: dpB)i.resize(2);
  for(auto& i: dpW)i.resize(2);
  for(auto& i: valid)i.resize(2);
  for(int i = 0; i <= n; i++)valid[i][0] = 1;
  auto stringify = [n](int x, int y){
    string ans = "";
    if(!valid[x][y])return (string)"INVALID";
    for(int i = 2; i < n+2; i++){
      //assert(dpW[n][k][i] || dpB[n][k][i]);
      if(dpW[x][y][i] && dpB[x][y][i]) ans += '?';
      else if(dpW[x][y][i]) ans += '_';
      else if(dpB[x][y][i]) ans += 'X';
      else ans += '!';
    }
    return ans;
  };
  for(int i = 2; i <= n+1; i++){
    valid[i][0] = 1, dpW[i][0] = dpW[i-1][0];
    dpW[i][0][i] = 1;
  }
  //cout << "hi" << endl;
  for(int j = 1; j <= k; j++){
    for(int i = 0; i < n+2; i++)dpW[i][j&1].reset(), dpW[i][j&1].reset(), valid[i][j&1] = 0;
    for(int i = 2; i < n+2; i++){
      if(i <= c[j-1] || !valid[i-c[j-1]-1][!(j&1)]){
        if(valid[i-1][j&1] && !targB[i]) dpW[i][j&1] = dpW[i-1][j&1], dpB[i][j&1] = dpB[i-1][j&1], dpW[i][j&1][i] = 1, valid[i][j&1] = 1;
        continue;
      }
      valid[i][j&1] = 1;
      dpW[i][j&1] = dpW[i-c[j-1]-1][!(j&1)];
      dpB[i][j&1] = dpB[i-c[j-1]-1][!(j&1)];
      //if(i != c[j-1])
      dpW[i][j&1][i-c[j-1]] = 1;
      for(int x = i-c[j-1]+1; x <= i; x++)dpB[i][j&1][x] = 1;
      //cout << i-1 << " " << j << " " << stringify(i, j) << endl;
      if(((dpB[i][j&1] & targW) | (dpW[i][j&1] & targB)).count())
        dpW[i][j&1] = dpW[i-1][j&1], dpB[i][j&1] = dpB[i-1][j&1], valid[i][j&1] = valid[i-1][j&1], dpW[i][j&1][i] = 1;
      else if(valid[i-1][j&1] && !targB[i]) dpW[i][j&1] |= dpW[i-1][j&1], dpB[i][j&1] |= dpB[i-1][j&1], dpW[i][j&1][i] = 1;
      if(dpW[i][j&1][i] && targB[i])valid[i][j&1] = 0, dpW[i][j&1][i] = 0;
      //cout << i-1 << " " << j << " " << stringify(i, j) << endl;
    }
  }
  return stringify(n+1, k&1);
}

• 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