Submission #116404

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
116404	2019-06-12 12:01:35	deinfreund	Paint By Numbers (IOI16_paint)	C++17	90 / 100	60 ms	38392 KiB

paint

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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;
    }
    
  }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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