제출 #232058

#제출 시각아이디문제언어결과실행 시간메모리
232058DS007Paint By Numbers (IOI16_paint)C++14
7 / 100
5 ms384 KiB
#include <bits/stdc++.h> using namespace std; string solve_puzzle(string s, vector<int> c) { int n = s.length() + 1, k = c.size(); s = " " + s; int pw[n] = {}, pb[n] = {}, black[n] = {}; for (int i = 1; i < n; i++) pw[i] = pw[i - 1] + (s[i] == '_'), pb[i] = pb[i - 1] + (s[i] == 'X'); bool dp1[n][k] = {}, check1[n][k] = {}; for (int i = c[0]; i < n; i++) { dp1[i][0] = pw[i] - pw[i - c[0]] == 0 && pb[i - c[0]] - pb[0] == 0; check1[i][0] = s[i] == 'X' ? dp1[i][0] : (dp1[i][0] || check1[i - 1][0]); //if (dp1[i][0]) // black[i - c[0] + 1] = max(black[i - c[0] + 1], c[0]); } for (int j = 1; j < k; j++) { for (int i = c[j] + 2; i < n; i++) { dp1[i][j] = pw[i] - pw[i - c[j]] == 0 && s[i - c[j]] != 'X' && check1[i - c[j] - 1][j - 1]; check1[i][j] = s[i] == 'X' ? dp1[i][j] : (dp1[i][j] || check1[i - 1][j]); //if (dp1[i][j]) // black[i - c[j] + 1] = max(black[i - c[j] + 1], c[j]); } } bool dp2[n][k] = {}, check2[n][k] = {}; for (int i = n - c[k - 1]; i >= 1; i--) { dp2[i][k - 1] = pw[i + c[k - 1] - 1] - pw[i - 1] == 0 && pb[n - 1] - pb[i + c[k - 1] - 1] == 0; check2[i][k - 1] = s[i] == 'X' ? dp2[i][k - 1] : (dp2[i][k - 1] || check2[i + 1][k - 1]); //if (dp2[i][k - 1]) // black[i] = max(black[i], c[k - 1]); } for (int j = k - 2; j >= 0; j--) { for (int i = n - c[j] - 2; i >= 1; i--) { dp2[i][j] = pw[i + c[j] - 1] - pw[i - 1] == 0 && s[i + c[j]] != 'X' && check2[i + c[j] + 1][j + 1]; check2[i][j] = s[i] == 'X' ? dp2[i][j] : (dp2[i][j] || check2[i + 1][j]); //if (dp2[i][j]) // black[i] = max(black[i], c[j]); } } for (int i = 1; i < n; i++) { if (dp2[i][0] && pb[i - 1] - pb[0] == 0) black[i] = max(black[i], c[0]); if (dp1[i][k - 1] && pb[n - 1] - pb[i] == 0) black[i - c[k - 1] + 1] = max(black[i - c[k - 1] + 1], c[k - 1]); } for (int i = 2; i < n; i++) { for (int j = 1; j < k; j++) if (dp2[i][j] && check2[i - 2][j - 1]) black[i] = max(black[i], c[j]); } bool isBlack[n] = {}, isWhite[n] = {}; for (int i = 1, j = 0; i < n; i++) { for (j = max(j, black[i]); i < n && j; j--, i++, j = max(j, black[i])) isBlack[i] = true; } for (int i = 1; i < n; i++) { if (s[i] == 'X') continue; isWhite[i] = s[i] == '_' || (check1[i - 1][k - 1] && pb[n - 1] - pb[i - 1] == 0) || (i != n - 1 && check2[i + 1][0] && pb[i] - pb[0] == 0); for (int j = 0; j < k - 1; j++) isWhite[i] = isWhite[i] || (check1[i - 1][j] && (i != n - 1 && check2[i + 1][j + 1])); } string ans = ""; for (int i = 1; i < n; i++) { assert(isWhite[i] || isBlack[i]); if (isWhite[i] && isBlack[i]) ans += '?'; else if (isWhite[i]) ans += '_'; else if (isBlack[i]) ans += 'X'; else ans += '?'; } 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...