제출 #296797

#제출 시각아이디문제언어결과실행 시간메모리
296797Haunted_CppPaint By Numbers (IOI16_paint)C++17
90 / 100
2063 ms511748 KiB
#include "paint.h" #include <bits/stdc++.h> using namespace std; const int MAX_N = 2e5 + 50; const int MAX_K = 1e2 + 5; bitset<2> vis[MAX_N][MAX_K]; bitset<2> dp[MAX_N][MAX_K]; bitset<2> calc[MAX_N][MAX_K]; vector<int> white, c, B; bitset<MAX_N> W; string s; int n, K; int range_sum(int lo, int hi) { hi = min(hi, n); return white[hi] - (lo - 1 >= 0 ? white[lo - 1] : 0); } int solve(int p, int k, bool can) { if (p >= n) return dp[p][k][can] = (k == K); if (calc[p][k][can]) return dp[p][k][can]; calc[p][k][can] = true; int res = 0; if (s[p] == '_' || s[p] == '.') { res = max(res, solve(p + 1, k, true)); } if (k < K && p + c[k] <= n && can && (s[p] == 'X' || s[p] == '.')) { const int cur = range_sum(p, p + c[k] - 1); if (cur == 0) { res = max(res, solve(min(n, p + c[k]), k + 1, false)); } } return dp[p][k][can] = res; } void backtrack(int p, int k, int can) { if (p >= n) { return; } if (vis[p][k][can]) { return; } vis[p][k][can] = 1; int white_works = 0; if (s[p] == '_' || s[p] == '.') { white_works = solve(p + 1, k, true); } int black_works = 0; if (k < K && can && (s[p] == 'X' || s[p] == '.')) { const int t = c[k]; if (p + t <= n) { const int cur = range_sum(p, p + t - 1); if (cur == 0) { black_works = solve(min(n, p + t), k + 1, false); } if (black_works) { ++B[p]; --B[min(n, p + t)]; backtrack(min(n, p + t), k + 1, false); } } } if (white_works) { W[p] = 1; backtrack(p + 1, k, true); } } string solve_puzzle(string s, vector<int> c) { ::c = c; ::s = s; n = s.size(); K = c.size(); white = vector<int>(n + 5); white[0] = (s[0] == '_'); for (int i = 1; i < n; i++) { white[i] = white[i - 1] + (s[i] == '_'); } B = vector<int>(n + 5); backtrack(0, 0, true); string res = string(n, 'z'); int cur = 0; for (int i = 0; i < n; i++) { cur += B[i]; if (cur > 0 && W[i] > 0) { res[i] = '?'; continue; } if (cur > 0) { res[i] = 'X'; continue; } if (W[i] > 0) { res[i] = '_'; continue; } } return res; }
#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...