제출 #762759

#제출 시각아이디문제언어결과실행 시간메모리
762759_martynasPaint By Numbers (IOI16_paint)C++11
59 / 100
1 ms724 KiB
#include "paint.h" #include <bits/stdc++.h> using namespace std; const int mxn = 2e5+5; const int mxk = 105; int n, k; int pref_b[mxn], pref_w[mxn]; bool dp[mxk][mxn], dp_pref[mxk][mxn]; bool must_b[mxn], can_b[mxn]; bool check(int pref[], int l, int r) { return pref[r] == pref[l-1]; } string solve_puzzle(string s, vector<int> C) { n = s.size(), k = C.size(); s = "$"+s; C.insert(C.begin(), -1); for(int i = 1; i <= n; i++) { pref_b[i] = pref_b[i-1]+(s[i]=='X'); pref_w[i] = pref_w[i-1]+(s[i]=='_'); } dp[0][0] = true; for(int i = C[0]; i <= n; i++) { if(s[i] != 'X') { dp_pref[0][i] = dp_pref[0][i-1]; } dp_pref[0][i] |= dp[0][i]; } for(int f = 1; f <= k; f++) { for(int i = C[f]; i <= n; i++) { if(((i > C[f] && dp_pref[f-1][i-C[f]-1]) || (i == C[f] && f == 1)) && check(pref_w, i-C[f]+1, i) && check(pref_b, i-C[f], i-C[f])) { dp[f][i] = true; } } for(int i = C[f]; i <= n; i++) { if(s[i] != 'X') { dp_pref[f][i] = dp_pref[f][i-1]; } dp_pref[f][i] |= dp[f][i]; } } // mark certain X for(int f = k, rmost_start = n; f > 0; f--) { int l = 0, r = n; int rmost = 0; for(int i = 0; i <= rmost_start; i++) { if(dp[f][i]) { r = min(r, i); l = max(l, i-C[f]+1); rmost = max(rmost, i); } } for(int i = l; i <= r; i++) { must_b[i] = true; } rmost_start = rmost-C[f]-1; } // mark possible X for(int f = k, rmost_start = n; f > 0; f--) { int cnt = 0; int rmost = 0; for(int i = rmost_start; i >= 0; i--) { if(dp[f][i]) { cnt = C[f]; rmost = max(rmost, i); } if(cnt > 0) can_b[i] = true; cnt--; } rmost_start = rmost-C[f]-1; } string ans(n, '?'); for(int i = 1; i <= n; i++) { if(!can_b[i]) { ans[i-1] = '_'; } else if(must_b[i]) { ans[i-1] = 'X'; } } return ans; } /* .......... 2 3 4 ........ 2 3 4 ..._._.... 1 3 .X........ 1 3 */
#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...