제출 #288686

#제출 시각아이디문제언어결과실행 시간메모리
288686IgorIPaint By Numbers (IOI16_paint)C++17
59 / 100
1 ms896 KiB
#include <bits/stdc++.h> using namespace std; #define all(x) (x).begin(), (x).end() #define forn(i, n) for (int (i) = 0; (i) < (n); (i)++) typedef vector<int> vi; typedef vector<vi> vvi; typedef long long ll; const int N = 200007; const int K = 103; int dpL[K][N]; int dpR[K][N]; string solve_puzzle(string s, vector<int> c) { s = "X." + s + ".X"; int k = c.size(); c.push_back(1); reverse(all(c)); c.push_back(1); reverse(all(c)); int n = s.size(); c[0] = 1, c[k + 1] = 1; dpL[0][0] = 1; dpR[k + 1][n - 1] = 1; for (int j = 1; j <= k; j++) { for (int i = 1; i < n; i++) { if (j == k) { int t = 1; for (int p = i + 1; p < n - 1; p++) if (s[p] == 'X') t = 0; if (!t) continue; } int L = i - c[j]; if (L < 0 || s[L] == 'X') continue; int t = 1; for (int f = L + 1; f <= i; f++) { if (s[f] == '_') { t = 0; break; } } if (!t) continue; for (int f = L - 1; f >= 0; f--) { if (dpL[j - 1][f]) { dpL[j][i] = 1; break; } if (s[f] == 'X') break; } } } for (int j = k; j >= 1; j--) { for (int i = n - 1; i >= 1; i--) { if (j == 1) { int t = 1; for (int p = i - 1; p > 0; p--) if (s[p] == 'X') t = 0; if (!t) continue; } int R = i + c[j]; if (R >= n + 1 || s[R] == 'X') continue; int t = 1; for (int f = i; f < R; f++) { if (s[f] == '_') { t = 0; break; } } if (!t) continue; for (int f = R + 1; f < n; f++) { if (dpR[j + 1][f]) { dpR[j][i] = 1; break; } if (s[f] == 'X') break; } } } vector<int> canX(s.size()), can_(s.size()); for (int j = 1; j < k + 1; j++) { for (int i = c[j]; i < n; i++) { if (dpL[j][i] && dpR[j][i - c[j] + 1]) { for (int p = i - c[j] + 1; p <= i; p++) { canX[p] = 1; } } else { dpL[j][i] = 0; dpR[j][i - c[j] + 1] = 0; } } } for (int i = 1; i < s.size(); i++) { for (int j = 0; j < k + 2; j++) { if (dpL[j][i - 1]) dpL[j][i] = 1; } } for (int i = s.size() - 2; i >= 0; i--) { for (int j = 0; j < k + 2; j++) { if (dpR[j][i + 1]) dpR[j][i] = 1; } } for (int i = 1; i < s.size() - 1; i++) { for (int j = 0; j + 1 < k + 2; j++) { if (dpL[j][i - 1] && dpR[j + 1][i + 1]) can_[i] = 1; } } string ans = ""; for (int i = 2; i < s.size() - 2; i++) { if (s[i] != '.') { ans += s[i]; continue; } if (canX[i] && can_[i]) ans += "?"; if (!canX[i]) ans += "_"; if (!can_[i]) ans += "X"; } return ans; }

컴파일 시 표준 에러 (stderr) 메시지

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:117:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |     for (int i = 1; i < s.size(); i++)
      |                     ~~^~~~~~~~~~
paint.cpp:131:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |     for (int i = 1; i < s.size() - 1; i++)
      |                     ~~^~~~~~~~~~~~~~
paint.cpp:139:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |     for (int i = 2; i < s.size() - 2; 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...