Submission #116427

#	Time	Username	Problem	Language	Result	Execution time	Memory
116427		deinfreund	Paint By Numbers (IOI16_paint)	C++17	100 / 100	730 ms	87468 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>

using namespace std;

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

vector<int> underlines;
vector<int> xes;

bool solvable(string & s, string & res, vector<int>& c, int spos, int cpos){
  long long pos = ((long long)cpos << 20) | spos;
  
  if (known[pos]) return cache[pos];
  //cout << "at " << spos << " with " << cpos << " remaining" << endl;
  if (spos >= s.size()) return cpos == c.size();
  bool sol = 0;
  if (cpos < c.size() && spos + c[cpos] <= s.size() && underlines[spos + c[cpos]] == underlines[spos] && (spos + c[cpos] == s.size() || s[spos + c[cpos]] != 'X')){
    if (solvable(s,res,c,spos + c[cpos] + 1, cpos+1)){
      //cout << "possible to put " << c[cpos] << " starting from " << spos << endl;
      xes[spos] = max(xes[spos],c[cpos]);
      if (spos + c[cpos] < s.size()) res[spos + c[cpos]] = '_';
      sol = sol || 1;
    }else{
      
      //cout << "impossible to put " << c[cpos] << " starting from " << spos << endl;
    }
  }
  if (s[spos] != 'X' && solvable(s, res, c, spos+1, cpos)){
    //cout << "possible to skip at " << spos << endl;
    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;
  underlines.resize(s.size() + 1);
  xes.resize(s.size());
  
  for (int i = 0; i < s.size(); i++){
    if (s[i] == '_') underlines[i+1] = underlines[i] + 1;
    else underlines[i+1] = underlines[i];
    //cout <<underlines[i];
  }
  //cout << endl;
  solvable(s,res,c, 0, 0);
  int Xrem = 0;
  for (int i = 0; i < s.size(); i++){
    Xrem = max(Xrem, xes[i]);
    if (Xrem > 0){
      if (res[i] == '.') res[i] = 'X';
      if (res[i] == '_') res[i] = '?';
    }
    
    Xrem--;
  }
  return res;
}

Compilation message (stderr)

paint.cpp: In function 'bool solvable(std::__cxx11::string&, std::__cxx11::string&, std::vector<int>&, int, int)':
paint.cpp:19:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (spos >= s.size()) return cpos == c.size();
       ~~~~~^~~~~~~~~~~
paint.cpp:19:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (spos >= s.size()) return cpos == c.size();
                                ~~~~~^~~~~~~~~~~
paint.cpp:21:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (cpos < c.size() && spos + c[cpos] <= s.size() && underlines[spos + c[cpos]] == underlines[spos] && (spos + c[cpos] == s.size() || s[spos + c[cpos]] != 'X')){
       ~~~~~^~~~~~~~~~
paint.cpp:21:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (cpos < c.size() && spos + c[cpos] <= s.size() && underlines[spos + c[cpos]] == underlines[spos] && (spos + c[cpos] == s.size() || s[spos + c[cpos]] != 'X')){
                          ~~~~~~~~~~~~~~~^~~~~~~~~~~
paint.cpp:21:122: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (cpos < c.size() && spos + c[cpos] <= s.size() && underlines[spos + c[cpos]] == underlines[spos] && (spos + c[cpos] == s.size() || s[spos + c[cpos]] != 'X')){
                                                                                                           ~~~~~~~~~~~~~~~^~~~~~~~~~~
paint.cpp:25:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if (spos + c[cpos] < s.size()) res[spos + c[cpos]] = '_';
           ~~~~~~~~~~~~~~~^~~~~~~~~~
paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:48:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < s.size(); i++){
                   ~~^~~~~~~~~~
paint.cpp:56:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < s.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: 10 / 10