| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1185926 | countless | Paint By Numbers (IOI16_paint) | C++20 | 0 ms | 0 KiB |
/*
Notes:
- dp as more than just a recurrence but a transition between states and overlapping subproblems
- i'm maining pacman on super smash bros
- i suck at dp
- - but i'm going to get better i swear (trust)
- ever since i was a jit......................XXXXX______.......... <-- solve 1 2 3 4 5
*/
#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 998244353;
const ll INF = 1e18;
const ld EPS = 1e-12;
#define endl "\n"
#define sp <<" "<<
#define REP(i, a, b) for(ll i = a; i < b; i++)
#define dbg(x) cout << #x << " = " << x << endl
#define mp make_pair
// #define pb push_back
#define fi first
#define se second
#define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())
#define try kwaz
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
template <typename Key, typename Value>
using hash_map = unordered_map<Key, Value, custom_hash>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// uniform_int_distribution<int>(a, b)(rng);
// shuffle(all(a), rng);
// i shamelessly had to read the editorial; cries and dies.
string solve_puzzle(string s, vector<int> c) {
int n = s.size(), k = c.size();
string t(s.rbegin(), s.rend());
vector<int> d(c.rbegin(), c.rend());
vector<int> pw(n+1, 0), pb(n+1, 0);
REP(i, 1, n+1) {
pw[i] = pw[i-1] + (s[i-1] == '_');
pb[i] = pb[i-1] + (s[i-1] == 'X');
}
auto try = [&](string ss, vector<int> &cc) -> vector<vector<bool>> {
vector<int> ppww(n+1, 0), ppbb(n+1, 0);
REP(i, 1, n+1) {
ppww[i] = ppww[i-1] + (ss[i-1] == '_');
ppbb[i] = ppbb[i-1] + (ss[i-1] == 'X');
}
vector<vector<bool>> res(n+1, vector<bool>(k+1, false));
res[0][0] = true;
REP(i, 1, n+1) {
if (ss[i-1] != '_') {
REP(j, 1, k+1) {
int l = i - cc[j-1];
int r = i;
if (j == 1) {
if (l >= 0 and ppbb[l] - ppbb[0] == 0 and ppww[r] - ppww[l] == 0)
res[i][j] = true;
}
else {
if (l >= 1 and ppww[r] - ppww[l] == 0 and ss[l-1] != 'X')
if (res[i - cc[j-1] - 1][j-1])
res[i][j] = true;
}
}
}
if (ss[i-1] != 'X') {
REP(j, 0, k+1) {
if (res[i-1][j])
res[i][j] = true;
}
}
}
return res;
};
vector<vector<bool>> dpf = try(s, c), dpb = try(t, d);
reverse(all(dpb));
vector<bool> cnw(n, false), cnb(n, false);
REP(i, 0, n) {
REP(j, 0, k+1) {
if (s[i] != 'X' and dpf[i][j] and dpb[i+1][k-j])
cnw[i] = true;
}
}
REP(i, 0, k) {
REP(j, 0, n - c[i] + 1) {
bool flag = true;
if (j > 0 and s[j-1] == 'X')
flag = false;
if (j + c[i] < n and s[j + c[i]] == 'X')
flag = false;
if (pw[j + c[i]] - pw[j] != 0)
flag = false;
if (!flag)
continue;
bool l = false, r = false;
if (i == 0 and j == 0)
l = true;
else if (j >= 1 and s[j-1] != 'X' and dpf[j-1][i])
l = true;
if (i == k - 1 and j + c[i] - 1 == n - 1)
r = true;
else if (j + c[i] - 1 < n - 1 and s[j + c[i]] != 'X' and dpb[j + c[i] + 1][k - i - 1])
r = true;
if (l and r)
REP(k, j, j + c[i])
cnb[k] = true;
}
}
string ans(n, '~');
REP(i, 0, n) {
if (cnw[i] and cnb[i])
ans[i] = '?';
else if (cnw[i])
ans[i] = '_';
else if (cnb[i])
ans[i] = 'X';
}
return ans;
}
signed main() {
string s; cin >> s;
vector<int> c;
int x;
while (cin >> x)
c.push_back(x);
cout << solve_puzzle(s, c) << endl;
}