Submission #116354

#	Time	Username	Problem	Language	Result	Execution time	Memory
116354		deinfreund	Paint By Numbers (IOI16_paint)	C++17	80 / 100	2055 ms	322208 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("O3")
unordered_map< long long, bool> cache;
unordered_map< long long, bool> known;

bool solvable(string & s, string & res, vector<int>& c, int remX, int spos, int cpos){
  long long pos = (long long)(remX+6) | ((long long )spos << 20LL ) | ( (long long)cpos << 40LL);
  if (known[pos]) return cache[pos];
  //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] = '?';
      cache[pos] = 1;
      known[pos] = 1;
      return 1;
    }
      known[pos] = 1;
    cache[pos] = 0;
    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())
      {
	sol = solvable(s,res,c, c[cpos+1], spos, cpos+1) || sol;
	cache[pos] = sol;
      known[pos] = 1;
	return sol;
      }
      known[pos] = 1;
    cache[pos] = 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:15:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (spos == s.size()) return cpos == c.size() -1 && remX <= 0;
       ~~~~~^~~~~~~~~~~
paint.cpp:15:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (spos == s.size()) return cpos == c.size() -1 && remX <= 0;
                                ~~~~~^~~~~~~~~~~~~~
paint.cpp:43:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (cpos +1< c.size())
         ~~~~~~~^~~~~~~~~~

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