제출 #139070

#제출 시각아이디문제언어결과실행 시간메모리
139070antimiragePaint By Numbers (IOI16_paint)C++14
59 / 100
3 ms504 KiB
#include "paint.h" #include <bits/stdc++.h> #define fr first #define sc second #define pb push_back #define mk make_pair #define all(s) s.begin(), s.end() using namespace std; const int N = 2e5 + 5; string ans; int k, pref[N][105], suf[N][105], n, cnt[N], fl[N], p[N]; string solve_puzzle(string s, vector<int> c) { c.insert(c.begin(), 0); n = s.size(); k = c.size() - 1; s = ' ' + s; pref[0][0] = 1; for (int i = 1; i <= n; i++) { cnt[i] = cnt[i - 1] + (s[i] == '_'); } for (int i = 1; i <= n; i++) { if (s[i] == '_') { for (int j = 0; j <= k; j++) { pref[i][j] = pref[i - 1][j]; } } else if (s[i] == 'X') { for (int j = 1; j <= k; j++) { if (i >= c[j] && cnt[i] - cnt[i - c[j]] == 0) { if (j == 1) { pref[i][j] = pref[i - c[j]][j - 1]; } else if (i >= c[j] + 1 && s[i - c[j]] != 'X') { pref[i][j] = pref[i - c[j] - 1][j - 1]; } } } } else { for (int j = 0; j <= k; j++) { pref[i][j] = pref[i - 1][j]; if (j > 0 && i >= c[j] && cnt[i] - cnt[i - c[j]] == 0) { if (j == 1) { pref[i][j] |= pref[i - c[j]][j - 1]; } else if (i >= c[j] + 1 && s[i - c[j]] != 'X') { pref[i][j] |= pref[i - c[j] - 1][j - 1]; } } } } } suf[n + 1][0] = 1; for (int i = n; i >= 1; i--) { if (s[i] == '_') { for (int j = 0; j <= k; j++) { suf[i][j] = suf[i + 1][j]; } } else if (s[i] == 'X') { for (int j = 1; j <= k; j++) { if (n - i + 1 >= c[k - j + 1] && cnt[i + c[k - j + 1] - 1] - cnt[i - 1] == 0) { if (j == 1) { suf[i][j] = suf[i + c[k - j + 1]][j - 1]; } else if (n - i + 1 >= c[k - j + 1] + 1 && s[i + c[k - j + 1]] != 'X') { suf[i][j] = suf[i + c[k - j + 1] + 1][j - 1]; } } } } else { for (int j = 0; j <= k; j++) { suf[i][j] = suf[i + 1][j]; if (j > 0 && n - i + 1 >= c[k - j + 1] && cnt[i + c[k - j + 1] - 1] - cnt[i - 1] == 0) { if (j == 1) { suf[i][j] |= suf[i + c[k - j + 1]][j - 1]; } else if (n - i + 1 >= c[k - j + 1] + 1 && s[i + c[k - j + 1]] != 'X') { suf[i][j] |= suf[i + c[k - j + 1] + 1][j - 1]; } } } } } for (int i = 1; i <= n; i++) { if (s[i] == 'X') continue; for (int j = 0; j <= k; j++) { if (pref[i - 1][j] && suf[i + 1][k - j]) { fl[i] = 1; break; } } } for (int i = 1; i <= n; i++) { if (s[i - 1] == 'X') continue; for (int j = 1; j <= k; j++) { if (i + c[j] - 1 > n || cnt[i + c[j] - 1] - cnt[i - 1] > 0) continue; if (k == 1) { if (i + c[j] - 1 <= n && pref[i - 1][j - 1] && suf[i + c[j]][k - j]){ p[i]++; p[i + c[j]]--; } } else { if (j == 1 && i + c[j] <= n && pref[i - 1][j - 1] && suf[i + c[j] + 1][k - j]) { p[i]++; p[i + c[j]]--; } else if (j == k && i >= 2 && i + c[j] - 1 <= n && pref[i - 2][j - 1] && suf[i + c[j]][k - j]) { p[i]++; p[i + c[j]]--; } else if (j > 1 && j < k && i >= 2 && i + c[j] <= n && pref[i - 2][j - 1] && suf[i + c[j] + 1][k - j]) { p[i]++; p[i + c[j]]--; } } } } for (int i = 1; i <= n; i++) { p[i] += p[i - 1]; if (s[i] == 'X') ans += 'X'; else if (s[i] == '_') ans += '_'; else { if (fl[i] && p[i]) ans += '?'; else if (fl[i]) ans += '_'; else ans += 'X'; } } 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...