Submission #116404

#	Time	Username	Problem	Language	Result	Execution time	Memory
116404		deinfreund	Paint By Numbers (IOI16_paint)	C++17	90 / 100	60 ms	38392 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("O3")
vector<bool> cache(1<<26);
vector<bool> known(1<<26);

bool solvable(string & s, string & res, string& c, int spos, int cpos){
  long long pos = ((long long)spos << 13) | cpos;
  
  if (known[pos]) return cache[pos];
  //cout << "at " << spos << " with " << remX <<"/" << c[cpos] << " remaining" << endl;
  if (spos == s.size()) return cpos == c.size();
  if (cpos < c.size() && s[spos] != c[cpos] && s[spos] != '.') {
    return 0;
  }
  bool sol = 0;
  if (cpos < c.size()) {
    if (solvable(s,res,c, spos+1, cpos+1)){
      if (c[cpos] == '_' && res[spos] == '.') res[spos] = '_';
      if (c[cpos] == '_' && res[spos] == 'X') res[spos] = '?';
      if (c[cpos] == 'X' && res[spos] == '.') res[spos] = 'X';
      if (c[cpos] == 'X' && res[spos] == '_') res[spos] = '?';
      sol= 1;
    }
    
  }
  if (s[spos] != 'X' && (cpos == c.size() || c[cpos] == '_') && solvable(s,res,c, spos+1, cpos)){
    //cout << "possible to skip at " << spos << endl;
    if (res[spos] == '.') res[spos] = '_';
    if (res[spos] == 'X') res[spos] = '?';
    sol = sol || 1;
  }
  known[pos] = 1;
  cache[pos] = sol;
  return sol;
}

std::string solve_puzzle(std::string s, std::vector<int> c) {
  string res = s;
  string cstr;
  for (int i = 0; i < c.size(); i++){
    cstr.push_back('_');
    for (int j = 0; j < c[i]; j++){
      cstr.push_back('X');
    }
  }
  solvable(s,res,cstr, 0, 0);
  solvable(s,res,cstr, 0, 1);
  return res;
}

Compilation message (stderr)

paint.cpp: In function 'bool solvable(std::__cxx11::string&, std::__cxx11::string&, std::__cxx11::string&, int, int)':
paint.cpp:16:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (spos == s.size()) return cpos == c.size();
       ~~~~~^~~~~~~~~~~
paint.cpp:16:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (spos == s.size()) return cpos == c.size();
                                ~~~~~^~~~~~~~~~~
paint.cpp:17:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (cpos < c.size() && s[spos] != c[cpos] && s[spos] != '.') {
       ~~~~~^~~~~~~~~~
paint.cpp:21:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (cpos < c.size()) {
       ~~~~~^~~~~~~~~~
paint.cpp:31:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (s[spos] != 'X' && (cpos == c.size() || c[cpos] == '_') && solvable(s,res,c, spos+1, cpos)){
                          ~~~~~^~~~~~~~~~~
paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:45:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < c.size(); i++){
                   ~~^~~~~~~~~~

• 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