제출 #595112

#제출 시각아이디문제언어결과실행 시간메모리
595112Valaki2Paint By Numbers (IOI16_paint)C++14
59 / 100
1 ms340 KiB
#include "paint.h" #include <bits/stdc++.h> using namespace std; #define pb push_back void calc_dp(int n, string s, int k, vector<int> c, vector<vector<int> > &cmin, vector<vector<int> > &cmax, vector<vector<bool> > &w) { cmin.assign(1 + n, vector<int> (1 + k, -1)); cmax.assign(1 + n, vector<int> (1 + k, -1)); w.assign(1 + n, vector<bool> (1 + k, false)); w[0][0] = true; for(int i = 1; i <= n; i++) { if(s[i] == 'X' || s[i] == '.') { for(int j = 1; j <= k; j++) { cmin[i][j] = n + 1; if(w[i - 1][j - 1]) { cmin[i][j] = 1; cmax[i][j] = 1; } if(cmin[i - 1][j] != -1) { cmin[i][j] = min(cmin[i][j], cmin[i - 1][j] + 1); cmax[i][j] = max(cmax[i][j], cmax[i - 1][j] + 1); } cmax[i][j] = min(cmax[i][j], c[j]); if(cmin[i][j] > cmax[i][j]) { cmin[i][j] = -1; cmax[i][j] = -1; } } } if(s[i] == '_' || s[i] == '.') { if(w[i - 1][0]) { w[i][0] = true; } for(int j = 1; j <= k; j++) { if(cmax[i - 1][j] == c[j]) { w[i][j] = true; } if(w[i - 1][j]) { w[i][j] = true; } } } } } vector<vector<int> > left_min; vector<vector<int> > left_max; vector<vector<bool> > left_w; vector<vector<int> > right_min; vector<vector<int> > right_max; vector<vector<bool> > right_w; string solve_puzzle(string s, vector<signed> c) { int n = (int) s.size(); int k = (int) c.size(); // calculate left dp string s1 = s; reverse(s1.begin(), s1.end()); s1.pb('!'); reverse(s1.begin(), s1.end()); vector<int> c1; c1.pb(0); for(int i = 0; i < k; i++) { c1.pb(c[i]); } calc_dp(n, s1, k, c1, left_min, left_max, left_w); // calculate right dp string s2 = s; s2.pb('!'); reverse(s2.begin(), s2.end()); vector<int> c2; for(int i = 0; i < k; i++) { c2.pb(c[i]); } c2.pb(0); reverse(c2.begin(), c2.end()); calc_dp(n, s2, k, c2, right_min, right_max, right_w); // calculate answer string ans(n, '!'); for(int i = 1; i <= n; i++) { bool b = false; int j1, j2, cur_left_min, cur_left_max, cur_right_min, cur_right_max; for(int idx = 1; idx <= k; idx++) { j1 = idx, j2 = k + 1 - idx; cur_left_min = left_min[i][j1]; cur_left_max = left_max[i][j1]; cur_right_max = right_min[n + 1 - i][j2]; cur_right_min = right_max[n + 1 - i][j2]; if(cur_left_min == -1 || cur_right_min == -1 || cur_left_max == -1 || cur_right_max == -1) { continue; } cur_right_max = c1[j1] + 1 - cur_right_max; cur_right_min = c1[j1] + 1 - cur_right_min; if(max(cur_left_min, cur_right_min) <= min(cur_left_max, cur_right_max)) { b = true; break; } } bool w = false; for(int idx = 0; idx <= k; idx++) { j1 = idx, j2 = k - idx; if(left_w[i][j1] && right_w[n + 1 - i][j2]) { w = true; break; } } char ch = '!'; if(b && w) { ch = '?'; } if(b && !w) { ch = 'X'; } if(!b && w) { ch = '_'; } ans[i - 1] = ch; } 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...