| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 963196 | ErJ | 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;
#define ll long long
#define vi vector<ll>
#define pp pair<ll, ll>
#define inf 1000000000000000000
#define vvi vector<vi>
#define vp vector<pp>
#define vvp vector<vp>
#define rep(i, n) for(int i = 0; i < n; i++)
#define mod 1000000007
vvi createDP(string s, vector<int> c) {
vvi dp(s.size());
vi pref_(s.size() + 1), prefX(s.size() + 1);
pref_[0] = 0;
prefX[0] = 0;
rep(i, dp.size()) {
pref_[i + 1] = pref_[i];
prefX[i + 1] = prefX[i];
if (s[i] == '_') pref_[i + 1]++;
if (s[i] == 'X') prefX[i + 1]++;
dp[i].resize(c.size() + 1);
rep(j, dp[i].size()) {
dp[i][j] = 0;
}
if (prefX[i + 1] == 0) dp[i][0] = 1;
else dp[i][0] = 0;
}
dp[0][0] = 1;
for (int i = 1; i < dp[0].size(); i++) {
dp[0][i] = 0;
}
for (int i = 1; i < dp.size(); i++) {
rep(j, dp[i].size()) {
if (s[i] != 'X') {
dp[i][j] = dp[i - 1][j];
}
if (j >= 1 && (i - c[j - 1] >= 0) && (pref_[i + 1] - pref_[i - c[j - 1] + 1] == 0)) {
if (j == 1) {
dp[i][j] = max(dp[i][j], dp[i - c[j - 1]][j - 1]);
}
else {
dp[i][j] = max(dp[i][j], dp[i - c[j - 1] - 1][j - 1]);
}
}
}
}
return dp;
}
string solve_puzzles(string s, vector<int> c) {
s = "__" + s + "__";
vi pref_(s.size() + 1), prefX(s.size() + 1);
pref_[0] = 0;
prefX[0] = 0;
rep(i, s.size()) {
pref_[i + 1] = pref_[i];
prefX[i + 1] = prefX[i];
if (s[i] == '_') pref_[i + 1]++;
if (s[i] == 'X') prefX[i + 1]++;
}
vvi dp = createDP(s, c);
string s2 = "";
vector<int> c2;
rep(i, s.size()) {
s2 += s[s.size() - 1 -i];
}
rep(i, c.size()) {
c2.push_back(c[c.size() - 1 - i]);
}
vvi dp2 = createDP(s2, c2);
vi canX(dp.size()), can_(dp.size());
for (int i = 1; i < dp.size() - 1; i++) {
can_[i] = 0;
canX[i] = 0;
rep(j, dp[i].size()) {
if (dp[i - 1][j] == 1 && dp2[dp2.size() - (i + 1) - 1][c.size() - j] == 1 && s[i] != 'X') {
can_[i] = 1;
}
}
}
rep(j, c.size()) {
for (int i = 2; i < dp.size() - 2; i++) {
ll start = i, end = i + c[j] - 1;
if (end >= s.size()) continue;
if (s[start - 1] != 'X' && s[end + 1] != 'X' && pref_[end + 1] - pref_[start - 1 + 1] == 0) {
if (end + 2 > dp.size() - 1) continue;
if (dp[start - 2][j] == 1 && dp2[dp2.size() - (end + 2) - 1][c.size() - 1 - j] == 1) {
canX[start]++;
canX[end + 1]--;
}
}
}
}
ll sumCanX = 0;
rep(i, canX.size()) {
sumCanX += canX[i];
if (sumCanX > 0) {
canX[i] = 1;
}
else {
canX[i] = 0;
}
}
string ans = "";
for (int i = 2; i < dp.size() - 2; i++) {
if (s[i] == '.') {
if (canX[i] == 1 && can_[i] == 1) {
ans += '?';
}
else if (canX[i] == 1) {
ans += 'X';
}
else {
ans += '_';
}
}
else {
ans += s[i];
}
}
return ans;
}