제출 #819985

#제출 시각아이디문제언어결과실행 시간메모리
819985KerimPaint By Numbers (IOI16_paint)C++17
90 / 100
2062 ms28268 KiB
#include "paint.h" #include "bits/stdc++.h" using namespace std; string solve_puzzle(string s, vector<int> c) { int n = s.size(), k = c.size(); s = "$" + s + "$"; vector<int> white(n+2, 0), black(n+2, 0); for (int i = 1; i <= n+1; i++){ white[i] = white[i-1] + (s[i] == '_'); black[i] = black[i-1] + (s[i] == 'X'); } reverse(c.begin(), c.end()); c.push_back(-1); reverse(c.begin(), c.end()); vector<vector<bool> > pref(n+3, vector<bool>(k+2, 0)); vector<vector<bool> > suf(n+3, vector<bool>(k+2, 0)); for (int i = 0; i <= n+2; i++){ pref[i][0] = black[i] == 0; suf[i][k+1] = black[n] == black[i - 1]; } for (int i = 1; i <= n; i++) for (int j = 1; j <= k; j++){ if (s[i] != 'X') pref[i][j] = pref[i-1][j]; if (i >= c[j] and white[i] == white[i-c[j]]){ if (i == c[j]){ if (j == 1) pref[i][j] = true; } else if (s[i-c[j]] != 'X') pref[i][j] = pref[i][j] | pref[i-c[j]-1][j-1]; } } for (int i = n; i >= 1; i--) for (int j = 1; j <= k; j++){ if (s[i] != 'X') suf[i][j] = suf[i+1][j]; if (i + c[j] <= n+1 and white[i+c[j]-1] == white[i-1] and s[i+c[j]] != 'X') suf[i][j] = suf[i][j] | suf[i+c[j]+1][j+1]; } //put white vector<int> answer(n+1, 0); for (int i = 1; i <= n; i++) if (s[i] == '.'){ for (int j = 1; j <= k+1; j++) if (pref[i-1][j-1] and suf[i+1][j]){ answer[i] |= 1; break; } } //put black for (int i = 1; i <= n; i++) if (s[i] == '.') for (int j = 1; j <= k; j++){ for (int h = max(i+c[j]-n,1); h <= min(i, c[j]); h++){ if (white[i + c[j] - h] != white[i - h]) continue; if (i - h >= 1 and s[i-h] == 'X') continue; if (i + c[j] - h + 1 <= n and s[i + c[j] - h + 1] == 'X') continue; if (i - h == 0){ if (j == 1 and suf[i+c[j]-h+2][j+1]) answer[i] |= 2; continue; } if (pref[i - h - 1][j-1] and suf[i+c[j]-h+2][j+1]) answer[i] |= 2; } } string result; for (int i = 1; i <= n; i++){ if (s[i] == '.'){ if (answer[i] == 1) result += '_'; else if(answer[i] == 2) result += 'X'; else result += '?'; } else result += s[i]; } return result; }
#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...