| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 772803 | Sharky | 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 <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 1;
const int maxk = 101;
int n, k, c[maxk], d[maxn];
string s;
bool L[maxn][maxk], R[maxn][maxk], possible[maxn][2];
int lst[maxn][maxk], nxt[maxn][maxk], lstw[maxn], nxtw[maxn], lstb[maxn], nxtb[maxn];
struct node {
int i, j, l, r;
node(int i, int j, int l, int r): i(i), j(j), l(l), r(r) {}
};
vector<node> b;
vector<pair<int, int>> st;
bool ok(int id) {
return (id >= 1 && id <= n);
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> s >> k;
n = s.length();
s = "a" + s;
s += 'a';
lstw[0] = lstb[0] = 0;
nxtb[n + 1] = nxtw[n + 1] = n + 1;
for (int i = 1; i <= n; i++) {
lstw[i] = lstw[i - 1];
lstb[i] = lstb[i - 1];
if (s[i] == '_') lstw[i] = i;
else if (s[i] == 'X') lstb[i] = i;
}
for (int i = n; i >= 1; i--) {
nxtb[i] = nxtb[i + 1];
nxtw[i] = nxtw[i + 1];
if (s[i] == '_') nxtw[i] = i;
else if (s[i] == 'X') nxtb[i] = i;
}
for (int i = 0; i <= n + 1; i++) for (int j = 0; j <= k; j++) lst[i][j] = nxt[i][j] = -1;
for (int i = 1; i <= k; i++) cin >> c[i];
for (int i = 0; i <= n; i++) {
if (s[i] == 'X') break;
lst[i][0] = i, L[i][0] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
lst[i][j] = lst[i - 1][j];
if (s[i] == '_') continue;
int idx = i - c[j];
if (idx < 0 || idx > n || s[idx] == 'X' || s[i+1] == 'X') continue;
int next_white = nxtw[idx + 1];
if (next_white <= i) continue;
if (idx == 0 && j > 1) continue;
if ((idx == 0 && j == 1) || lst[idx - 1][j - 1] != -1) {
if (!(idx == 0 && j == 1)) {
int pos = lst[idx - 1][j - 1];
int next_black = nxtb[pos + 1];
if (next_black <= idx) continue;
// cout << "debug: " << idx << ' ' << j << ' ' << lst[idx - 1][j - 1] << '\n';
}
L[i][j] = 1;
lst[i][j] = i;
b.emplace_back(i, j, idx + 1, i);
}
// cout << i << ' ' << j << ' ' << L[i][j] << '\n';
}
}
for (int i = n + 1; i >= 1; i--) {
if (s[i] == 'X') break;
nxt[i][0] = i, R[i][0] = 1;
}
reverse(c + 1, c + k + 1);
for (int i = n; i >= 1; i--) {
for (int j = 1; j <= k; j++) {
nxt[i][j] = nxt[i + 1][j];
if (s[i] == '_') continue;
int idx = i + c[j];
if (idx <= 0 || idx > n + 1 || s[idx] == 'X' || s[i-1] == 'X') continue;
int last_white = lstw[idx - 1];
if (last_white >= i) continue;
if (idx == n + 1 && j > 1) continue;
if ((idx == n + 1 && j == 1) || nxt[idx + 1][j - 1] != -1) {
if (!(idx == n + 1 && j == 1)) {
int pos = nxt[idx + 1][j - 1];
int next_black = lstb[pos - 1];
if (next_black >= idx) continue;
// cout << "debug: " << idx << ' ' << j << ' ' << lst[idx - 1][j - 1] << '\n';
}
R[i][j] = 1;
nxt[i][j] = i;
}
// cout << i << ' ' << j << ' ' << R[i][j] << '\n';
}
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
if (lst[i - 1][j] != -1 && nxt[i + 1][k - j] != -1 && s[i] != 'X') possible[i][0] = 1;
}
}
for (auto& [i, j, l, r] : b) {
if (i == n && j != k) continue;
if (i == n || (L[i][j] && s[i + 1] != 'X' && nxt[i + 2][k - j] != -1)) {
d[l]++, d[r + 1]--;
// cout << l << ' ' << r << '\n';
}
}
for (int i = 1; i <= n; i++) {
d[i] += d[i - 1];
possible[i][1] = !!(d[i] > 0);
}
for (int i = 1; i <= n; i++) {
if (possible[i][0] && possible[i][1]) cout << '?';
else if (possible[i][0]) cout << '_';
else if (possible[i][1]) cout << 'X';
// else assert(false);
}
cout << '\n';
}