Submission #1051007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051007		fv3	Paint By Numbers (IOI16_paint)	C++14	7 / 100	1 ms	360 KiB

paint

#include<bits/stdc++.h>
#include"paint.h"
using namespace std;string solve_puzzle(string s, vector<int> c){const int K = c.size();const int N = s.size();s = "_" + s + "_";vector<int> preSum(N+3);for (int i = 0; i <= N + 2; i++)preSum[i+1] = preSum[i] + (int)(s[i] == '_');vector<vector<int>> DP_r(N+2, vector<int>(K+1));DP_r[0][0] = 1;for (int i = 0; i <= N; i++){if (s[i] == 'X') continue;for (int k = 0; k <= K; k++){if (!DP_r[i][k]) continue;if (s[i + 1] != 'X')DP_r[i+1][k] = 1;if (k == K || i + c[k] + 1 >= N + 2) continue;if (preSum[i + c[k] + 1] - preSum[i + 1]) continue;if (s[i + c[k] + 1] == 'X') continue;DP_r[i + c[k] + 1][k + 1] = 1;}}vector<vector<int>> DP_l(N+2, vector<int>(K+1));DP_l[N+1][K] = 1;for (int i = N+1; i >= 1; i--){if (s[i] == 'X') continue;for (int k = 0; k <= K; k++){if (!DP_l[i][k]) continue;if (s[i - 1] != 'X')DP_l[i-1][k] = 1;if (k == 0 || i - c[k-1] - 1 < 0) continue;if (preSum[i] - preSum[i - c[k-1]]) continue;if (s[i - c[k-1] - 1] == 'X') continue;DP_l[i - c[k-1] - 1][k - 1] = 1;}}vector<int> ps(N+2);for (int i = 0; i < N + 2; i++){if (s[i] == 'X') continue;for (int k = 0; k < K; k++){if (i + c[k] + 1 >= N + 2 || !DP_r[i][k] || !DP_l[i + c[k] + 1][k+1]) continue;if (i + c[k] + 1 >= N + 2) continue;if (preSum[i + c[k] + 1] - preSum[i + 1]) continue;if (s[i + c[k] + 1] == 'X') continue;ps[i+1]++;ps[i+c[k]+1]--;}}string res(N, '_');int sum = 0;for (int i = 1; i <= N; i++){sum += ps[i];if (s[i] == 'X'){res[i-1] = 'X';continue;}if (sum){bool ok = true;for (int k = 0; k <= K; k++){if (!DP_r[i][k] || !DP_l[i][k]) continue;ok = false;res[i-1] = '?';break;}if (ok) res[i-1] = 'X';}}return res;}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 3
• Subtask 3: 0 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10