| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 296792 | Haunted_Cpp | Paint By Numbers (IOI16_paint) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5 + 500;
const int MAX_K = 1e2 + 500;
bitset<2> vis[MAX_N][MAX_K];
bitset<2> dp[MAX_N][MAX_K];
bitset<2> calc[MAX_N][MAX_K];
vector<int> white, c, B;
bitset<MAX_N> W;
string s;
int n, K;
int range_sum(int lo, int hi) {
return white[hi] - (lo - 1 >= 0 ? white[lo - 1] : 0);
}
int solve(int p, int k, bool can) {
if (p >= n) return dp[p][k][can] = (k == K);
if (calc[p][k][can]) return dp[p][k][can];
calc[p][k][can] = true;
int res = 0;
if (s[p] == '_' || s[p] == '.') {
res = max(res, solve(p + 1, k, true));
}
if (k < K && p + c[k] <= n && can && (s[p] == 'X' || s[p] == '.')) {
const int cur = range_sum(p, p + c[k] - 1);
if (cur == 0) {
res = max(res, solve(p + c[k], k + 1, false));
}
}
return dp[p][k][can] = res;
}
void backtrack(int p, int k, int can) {
if (p >= n) {
return;
}
if (vis[p][k][can]) {
return;
}
vis[p][k][can] = 1;
int white_works = 0;
if (s[p] == '_' || s[p] == '.') {
white_works = solve(p + 1, k, true);
}
int black_works = 0;
if (k < K && can && (s[p] == 'X' || s[p] == '.')) {
const int t = c[k];
if (p + t <= n) {
const int cur = range_sum(p, p + t - 1);
if (cur == 0) {
black_works = solve(p + t, k + 1, false);
}
if (black_works) {
++B[p];
--B[min(n, p + t)];
backtrack(p + t, k + 1, false);
}
}
}
if (white_works) {
W[p] = 1;
backtrack(p + 1, k, true);
}
}
string solve_puzzle(string s, vector<int> c) {
::c = c;
::s = s;
n = s.size();
K = c.size();
white = vector<int>(n);
white[0] = (s[0] == '_');
for (int i = 1; i < n; i++) {
white[i] = white[i - 1] + (s[i] == '_');
}
B = vector<int>(n + 5);
backtrack(0, 0, true);
string res = string(n, 'z');
int cur = 0;
for (int i = 0; i < n; i++) {
cur += B[i];
if (cur > 0 && W[i] > 0) {
res[i] = '?';
continue;
}
if (cur > 0) {
res[i] = 'X';
continue;
}
if (W[i] > 0) {
res[i] = '_';
continue;
}
}
return res;
}