Submission #116343

#	Time	Username	Problem	Language	Result	Execution time	Memory
116343		deinfreund	Paint By Numbers (IOI16_paint)	C++14	10 / 100	2025 ms	504 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>

using namespace std;

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

std::string solve_puzzle(std::string s, std::vector<int> c) {
  string res = s;
  solvable(s,res,c, -1, 0, -1);
  return res;
}

Compilation message (stderr)

paint.cpp: In function 'bool solvable(std::__cxx11::string&, std::__cxx11::string&, std::vector<int>&, int, int, int)':
paint.cpp:9:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (spos == s.size()) return cpos == c.size() -1 && remX <= 0;
       ~~~~~^~~~~~~~~~~
paint.cpp:9:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (spos == s.size()) return cpos == c.size() -1 && remX <= 0;
                                ~~~~~^~~~~~~~~~~~~~
paint.cpp:29:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (cpos +1< c.size()) return solvable(s,res,c, c[cpos+1], spos, cpos+1) || sol;
         ~~~~~~~^~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 0 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10