| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 241695 | crossing0ver | 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>
//#include "paint.h"
using namespace std;
int n;
int x[1000000],dpL[300000][102][2],dpR[300000][102][2],black[300000],L[2][300005],R[2][300005],white[300000];
vector<int> c;
void checkL(int pos,int k) {
for (int i = 0; i < 2; i++) {
if (x[pos] == 0 && i == 1) continue;
if (x[pos] == 1 && i == 0) continue;
if (i == 0)
dpL[pos][k][0] = (dpL[pos-1][k][0]|dpL[pos-1][k][1])|(c[k] == 0 && L[1][pos] == 0);
if (i == 1) {
if (pos - L[0][pos] < c[k] || c[k] == 0) {
dpL[pos][k][1] = 0;
continue;
}
dpL[pos][k][1] = dpL[pos - c[k]][k-1][0];
}
}
// cout << pos << " " << k <<' ' << dpL[pos][k][1]<<'\n';
}
void checkR(int pos,int k) {
for (int i = 0; i < 2; i++) {
if (x[pos] == 0 && i == 1) continue;
if (x[pos] == 1 && i == 0) continue;
if (i == 0) {
dpR[pos][k][0] = (dpR[pos + 1][k][0]|dpR[pos+1][k][1])|(c[k] == 0 && R[1][pos] == n+1);
}
if (i == 1) {
if (i + c[k] > R[0][i] || c[k] == 0) {
dpR[pos][k][1] = 0;
continue;
}
dpR[pos][k][1] = dpR[pos + c[k]][k+1][0];
}
}
}
string solve_puzzle(string s, vector<int> c1) {
// preprocess
s = "#" + s;
n = (int)s.size() - 1;
int k = c1.size();
for (int i = 1; i <= n; i++) {
if (s[i] == 'X') {
x[i] = 1;
L[0][i] = L[0][i-1];
L[1][i] = R[1][i] = i;
}
else if (s[i] == '_') {
x[i] = 0;
L[0][i] = R[0][i] = i;
L[1][i] = L[1][i-1];
}
else {
x[i] = 2;
L[0][i] = L[0][i-1];
L[1][i] = L[1][i-1];
}
}
R[0][n+1] = R[1][n+1] = n+1;
for (int i = n; i > 0; i--) {
if (s[i] == 'X')
R[0][i] = R[0][i+1];
else if (s[i] == '_') R[1][i] = R[1][i+1];
else {
R[0][i] = R[0][i+1];
R[1][i] = R[1][i+1];
}
}
//for (int i = 1; i <= n; i++) cout << L[1][i] <<" "<<R[1][i]<<'\n';
c.push_back(0);
for (int i : c1) c.push_back(i);
k++;
c.push_back(0);
k++;
// preprecessing done
dpL[0][0][0] = 1;
dpR[n+1][k-1][0] = 1;
for (int i = 1;i <= n; i++)
for (int j = 0; j <= k-1; j++)
checkL(i,j);
// cout << n <<'\n';
for (int i = n; i > 0; i--)
for (int j = k-1; j >= 0; j--) {
checkR(i,j);
}
// cout << dpL[3][0][0] <<' '<<dpL[3][1][1] <<' '<<dpL[2][0][0];
for (int i = 1;i <= n; i++) {
for (int j = 0; j < k;j++) {
if (dpL[i][j][0] == 1 && (dpR[i][j+1][0] == 1) )
white[i] = 1;
for (int e = i; e < i + c[j]; e++)
black[i]|= (dpL[e][j][1] & dpR[e+1][j+1][0]);
}
}
string ans;
for (int i = 1; i <= n; i++) {
if (white[i] && black[i]) ans += "?";
else if (white[i]) ans+="_";
else ans += "X";
}
return ans;
}
main() {
string s; cin >> s;
int n; cin >> n;
vector<int> c1(n);
for (int i = 0,j; i < n;i++){
cin >> j;
c1[i] = j;
}
cout << solve_puzzle(s,c1);
}
/* ..........
2 3 4
*/