제출 #116425

#제출 시각아이디문제언어결과실행 시간메모리
116425deinfreundPaint By Numbers (IOI16_paint)C++17
80 / 100
49 ms33784 KiB
#include "paint.h" #include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O3") vector<bool> cache(1<<26); vector<bool> known(1<<26); 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; }

컴파일 시 표준 에러 (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++){
                   ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...