제출 #598791

#제출 시각아이디문제언어결과실행 시간메모리
598791jophyyjhPaint By Numbers (IOI16_paint)C++14
59 / 100
1 ms340 KiB
/** * Nice little problem. O(nk) may work, so let's just do dp. Well, this problem * mainly tests a contestant's fundamentals, e.g. things like prefix sum, dp, * difference array, etc. Really tedious to code... * If i met such problem in the real contest, i definitely cannot AC it. It just took * me too long to code... * * Time Complexity: O(nk) * Implementation 1 */ #include <bits/stdc++.h> #include "paint.h" typedef std::vector<int> vec; template<class T> struct Array2D { T* values; int _w; Array2D(int h, int w) { values = new T[h * w], _w = w; } ~Array2D() { delete [] values; } inline T* operator[](int x) { return values + x * _w; } }; std::string solve_puzzle(std::string str, std::vector<int> c) { int n = str.size(), seg = c.size(); vec prefix_b(n + 1), prefix_w(n + 1); // pre.sum. of black & w prefix_b[0] = prefix_w[0] = 0; for (int i = 1; i <= n; i++) { prefix_b[i] = prefix_b[i - 1] + (str[i - 1] == 'X'); prefix_w[i] = prefix_w[i - 1] + (str[i - 1] == '_'); } // dp1[i][s] = if it's possible for the first s segments end no later than the // i-th position (but the first s+1 segments do not) Array2D<bool> dp1(n + 1, seg + 1), dp2(n + 2, seg + 1); // fwd & back dir dp1[0][0] = dp2[n + 1][0] = 1; for (int s = 1; s <= seg; s++) dp1[0][s] = 0, dp2[n + 1][s] = 0; for (int i = 1; i <= n; i++) { for (int s = 0; s <= seg; s++) { dp1[i][s] = false; dp1[i][s] |= (dp1[i - 1][s] && str[i - 1] != 'X'); if (s > 0 && i - c[s - 1] - (s > 1) >= 0) { dp1[i][s] |= (dp1[i - c[s - 1] - (s > 1)][s - 1] && prefix_w[i] - prefix_w[i - c[s - 1]] == 0); } } } for (int i = n; i >= 1; i--) { for (int s = 0; s <= seg; s++) { dp2[i][s] = false; dp2[i][s] |= (dp2[i + 1][s] && str[i - 1] != 'X'); if (s > 0 && i + c[seg - s] + (s > 1) <= n + 1) { dp2[i][s] |= (dp2[i + c[seg - s] + (s > 1)][s - 1] && prefix_w[i + c[seg - s] - 1] - prefix_w[i - 1] == 0); } } } std::vector<bool> can_b(n), can_w(n); for (int i = 1; i <= n; i++) { can_w[i - 1] = false; for (int l = 0; l <= seg && !can_w[i - 1] && str[i - 1] != 'X'; l++) can_w[i - 1] = (str[i - 1] != 'X' && dp1[i - 1][l] && dp2[i + 1][seg - l]); if (str[i - 1] == '_') assert(can_w[i - 1]); } vec diff(n + 1, 0); // difference array for black for (int i = 0; i < n; i++) { for (int s = 0; s < seg; s++) { if (i - c[s] + (s == 0) >= 0 && i + 2 + (s < seg - 1) <= n + 1 && dp1[i - c[s] + (s == 0)][s] && dp2[i + 2 + (s < seg - 1)][seg - s - 1] && prefix_w[i + 1] - prefix_w[i - c[s] + 1] == 0) { bool more_check = true; if (s > 0) more_check &= (str[i - c[s]] != 'X'); if (s < seg - 1) more_check &= (str[i + 1] != 'X'); if (more_check) { int l = i - c[s] + 1, r = i; diff[l]++, diff[r + 1]--; } } } } for (int i = 0, prefix_sum = 0; i < n; i++) { prefix_sum += diff[i]; can_b[i] = (prefix_sum > 0); assert(str[i] != '_' || !can_b[i]); if (str[i] == 'X') assert(can_b[i] && !can_w[i]); } std::string ans; for (int i = 0; i < n; i++) { assert(can_b[i] || can_w[i]); if (can_b[i] && can_w[i]) ans.push_back('?'); else if (can_b[i]) ans.push_back('X'); else ans.push_back('_'); } return ans; }
#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...