| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1150794 | Angus_Yeung | Paint By Numbers (IOI16_paint) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define ok first
#define bk second
using namespace std;
typedef long long ll;
ll n, k, c[110], b[200010], w[200010], pt1, pt2, l, r;
pair<bool, int> dp1[110][200010], dp2[110][200010];
string s;
ll p1[200010], p2[200010], tmp;
ll len[200010];
ll mxx(ll l, ll r) {
ll res = 0;
for (int i = l; i <= r; i++) res = max(res, c[i]);
return res;
}
int main() {
cin.tie(0); cout.tie(0);
ios::sync_with_stdio(0);
cin >> s;
n = s.length();
s = ' '+s;
b[0] = w[0] = 0;
for (int i = 1; i <= n; i++) {
b[i] = w[i] = 0;
if (s[i] == 'X') b[i]++;
else if (s[i] == '_') w[i]++;
b[i] += b[i-1];
w[i] += w[i-1];
p1[i] = p2[i] = 0;
}
cin >> k;
for (int i = 1; i <= k; i++) cin >> c[i];
for (int j = c[1]; j <= n; j++) {
l = j-c[1]+1; r = j;
if (!(b[l-1]) && !(w[r]-w[l-1])) dp1[1][j].ok = 1;
else dp1[1][j].ok = 0;
}
for (int i = 2; i <= k; i++) {
pt1 = 0;
for (int j = c[i]; j <= n; j++) {
l = j-c[i]+1; r = j;
while (pt1 <= l-2 && (!dp1[i-1][pt1].ok || b[l-1]-b[pt1])) pt1++;
if (pt1 <= l-2 && dp1[i-1][pt1].ok && !(b[l-1]-b[pt1]) && !(w[r]-w[l-1])) {
dp1[i][j].ok = 1;
dp1[i][j].bk = pt1;
} else {
dp1[i][j].ok = 0;
}
}
}
for (int i = 1; i <= n; i++) {
if (dp1[k][i].ok && !(b[n]-b[i])) {
tmp = i;
break;
}
}
for (int i = k; i >= 1; i--) {
for (int j = tmp-c[i]+1; j <= tmp; j++) p1[j] = i;
tmp = dp1[i][tmp].bk;
}
for (int j = n-c[k]+1; j >= 1; j--) {
l = j; r = j+c[k]-1;
if (!(b[n]-b[r]) && !(w[r]-w[l-1])) dp2[k][j].ok = 1;
else dp2[k][j].ok = 0;
}
for (int i = k-1; i >= 1; i--) {
pt2 = n;
for (int j = n-c[i]+1; j >= 1; j--) {
l = j; r = j+c[i]-1;
while (pt2 >= r+2 && (!dp2[i+1][pt2].ok || b[pt2-1]-b[r])) pt2--;
if (pt2 >= r+2 && dp2[i+1][pt2].ok && !(b[pt2-1]-b[r]) && !(w[r]-w[l-1])) {
dp2[i][j].ok = 1;
dp2[i][j].bk = pt2;
} else {
dp2[i][j].ok = 0;
}
}
}
for (int i = n; i >= 1; i--) {
if (dp2[1][i].ok && !(b[i-1])) {
tmp = i;
break;
}
}
for (int i = 1; i <= k; i++) {
for (int j = tmp; j <= tmp+c[i]-1; j++) p2[j] = i;
tmp = dp2[i][tmp].bk;
}
len[0] = 0;
for (int i = 1; i <= n; i++) {
if (s[i] == '_') len[i] = 0;
else len[i] = len[i-1]+1;
}
for (int i = n; i >= 1; i--) {
if (len[i] != 0 && len[i+1] > len[i]) len[i] = len[i+1];
}
pt1 = pt2 = 0;
for (int i = 1; i <= n; i++) {
pt1 = max(pt1, p1[i]);
pt2 = max(pt2, p2[i]);
if (s[i] != '.') cout << s[i];
else if (p1[i] == p2[i]) {
if (p1[i]) cout << 'X';
else if (pt1 == pt2) cout << '_';
else if (len[i] < mxx(pt2+1, pt1)) cout << '_';
else cout << '?';
} else {
cout << '?';
}
}
cout << "\n";
return 0;
}