제출 #770587

#제출 시각아이디문제언어결과실행 시간메모리
770587_martynasPaint By Numbers (IOI16_paint)C++11
90 / 100
2071 ms6352 KiB
#include "paint.h" #include <bits/stdc++.h> using namespace std; const int mxn = 2e5+5; const int mxk = 105; /* 1. Craft a pseudo function that returns a boolean vector for each x "block" times each position. [b][i] - true if it's possible to place first b+1 blocks and the b-th one ending at i-th position 2. Run this function once 3. Reverse inputs 4. Run this function again and reverse it's results 5. If both endpoints of a block at some position are true then some valid covering uses that block there. (Finding possible X characters done) 6. To find optional X places try "skipping" them, i.e. going form b to b+1 blocks where b-th ends before them and b+1-th starts after them. */ int n, k; bool can_X[mxn], can_skip[mxn]; vector<vector<bool>> calc(string s, vector<int> C) { vector<vector<bool>> dp(k, vector<bool>(n)); for(int b = 0; b < k; b++) { bool last_reachable = b == 0; for(int i = C[b]-1; i < n; i++) { if(i >= C[b] && s[i-C[b]] == 'X') { last_reachable = false; } if(i >= C[b]+1 && s[i-C[b]] != 'X' && (b > 0 && dp[b-1][i-C[b]-1])) { last_reachable = true; } if(last_reachable && count(s.begin()+i-C[b]+1, s.begin()+i+1, '_') == 0) { dp[b][i] = true; } } } return dp; } string solve_puzzle(string s, vector<int> C) { n = s.size(); k = C.size(); auto dpL = calc(s, C); reverse(s.begin(), s.end()); reverse(C.begin(), C.end()); auto dpR = calc(s, C); reverse(s.begin(), s.end()); reverse(C.begin(), C.end()); for(int b = 0; b < k; b++) { reverse(dpR[b].begin(), dpR[b].end()); } reverse(dpR.begin(), dpR.end()); // all possible blocks for(int b = 0; b < k; b++) { for(int i = C[b]-1, rm = 0; i < n; i++) { if(dpL[b][i] && dpR[b][i-C[b]+1]) { for(int j = max(rm, i-C[b]+1); j <= i; j++) { can_X[j] = true; } rm = i; } } } // all possible skipped positions // don't forget skipping rightmost positions // this is O(nk) ... probably for(int b = 0, rm_done = 0; b < k; b++) { int from = b == 0 ? 0 : n+1; for(int i = C[b]-1; i < n; i++) { if(i >= C[b] && s[i-C[b]] == 'X') { from = n+1; } if(i >= C[b]+1 && s[i-C[b]] != 'X' && (b > 0 && dpL[b-1][i-C[b]-1] && dpR[b-1][i-C[b]-C[b-1]])) { from = min(from, i-C[b]); } if(dpL[b][i] && dpR[b][i-C[b]+1]) { for(; from <= i-C[b]; from++) { can_skip[from] = true; } if(!rm_done && b == k-1) { for(int j = i+1; j < n; j++) { can_skip[j] = true; } rm_done = true; } } } } string ans(n, '9'); for(int i = 0; i < n; i++) { if(!can_X[i]) { ans[i] = '_'; } else if(!can_skip[i]) { ans[i] = 'X'; } else { ans[i] = '?'; } } return ans; } /* .X.X._.X_.. 2 3 2 ..X.._.X_.. 2 3 2 sample: .......... 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...