#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
string s;
vector <int> c;
int n, m;
const int maxnk = 101;
bool ready[maxnk][maxnk][maxnk];
bool dp[maxnk][maxnk][maxnk];
bool solve(int len, int i, int j) {
if (len < -1)
return false;
if (len <= 0) {
return i > j;
}
if (i > j)
return true;
if (ready[len][i][j])
return dp[len][i][j];
bool ans = solve(len - c[i] - 1, i+1, j);
ans |= solve(len - 1, i, j);
dp[len][i][j] = ans;
ready[len][i][j] = true;
return ans;
}
string solve_puzzle(string S, vector<int> C) {
s = S;
c = C;
n = S.size();
m = c.size();
string ans;
ans.resize(n, '?');
int pt = 0;
int len = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '.')
len++;
else {
int x = 0, len2 = 0;
while (pt < m && len2 + C[pt] <= len) {
len2 += C[pt];
pt++;
x++;
len2++;
}
vector <vector <int>> st(2);
int cur = 1;
int prev = 0;
for (int j = 0; j < len; j++)
st[prev].push_back(n - j - 1);
for (int j = pt - x; j < pt; j++) {
st[cur].clear();
for (auto k : st[prev]) {
if (solve(n - k, j, pt-1))
st[cur].push_back(k + C[j] + 1);
}
if ((int)st[cur].size() == 1) {
for (int k = 1; k <= C[j]; k++)
ans[st[cur].back() - k - 1] = 'X';
if (j+1 < pt && st[cur].back() - 1 < n)
ans[st[cur].back() - 1] = '_';
} else if ((int)st[cur].size() > 1 && C[j] > 1) {
for (int k = 2; k < C[j] - 1; k++)
ans[st[cur].back() - k - 1] = 'X';
ans[st[cur].back() - 1 - 1] = 'X';
}
swap(prev, cur);
}
}
}
if (len > 0) {
int x = 0, len2 = 0;
while (pt < m && len2 + C[pt] <= len) {
len2 += C[pt];
pt++;
x++;
len2++;
}
vector <vector <int>> st(2);
int cur = 1;
int prev = 0;
for (int j = 0; j < len; j++)
st[prev].push_back(n - j - 1);
for (int j = pt - x; j < pt; j++) {
st[cur].clear();
for (auto k : st[prev]) {
if (solve(n - k, j, pt-1))
st[cur].push_back(k + C[j] + 1);
}
if ((int)st[cur].size() == 1) {
for (int k = 1; k <= C[j]; k++)
ans[st[cur].back() - k - 1] = 'X';
if (j+1 < pt && st[cur].back() - 1 < n)
ans[st[cur].back() - 1] = '_';
} else if ((int)st[cur].size() > 1 && C[j] > 1) {
for (int k = 2; k < C[j] - 1; k++)
ans[st[cur].back() - k - 1] = 'X';
ans[st[cur].back() - 1 - 1] = 'X';
}
swap(prev, cur);
}
}
return ans;
}
// int main() {
// string tp;
// cin >> tp;
// int clen;
// cin >> clen;
// vector <int> c(clen);
// for (int i = 0; i < clen; i++)
// cin >> c[i];
// cout << solve_puzzle(tp, c) << '\n';
// }
Compilation message
shortcut.cpp:1:10: fatal error: paint.h: No such file or directory
1 | #include "paint.h"
| ^~~~~~~~~
compilation terminated.
