| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 288714 | IgorI | Paint By Numbers (IOI16_paint) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define forn(i, n) for (int (i) = 0; (i) < (n); (i)++)
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long ll;
const int N = 200007;
const int K = 103;
int dpL[K][N];
int dpR[K][N];
int cnt_[N];
int prevX[N], nextX[N];
string solve_puzzle(string s, vector<int> c)
{
s = "X." + s + ".X";
int k = c.size();
c.push_back(1);
reverse(all(c));
c.push_back(1);
reverse(all(c));
int n = s.size();
for (int i = 1; i < s.size(); i++)
{
cnt_[i] = cnt_[i - 1] + (s[i] == '_');
}
for (int i = 1; i < s.size(); i++)
{
prevX[i] = prevX[i - 1];
if (s[i] == 'X') prevX[i] = i;
}
nextX[s.size() - 1] = s.size() - 1;
for (int i = s.size() - 2; i >= 0; i--)
{
nextX[i] = nextX[i + 1];
if (s[i] == 'X') nextX[i] = i;
}
c[0] = 1, c[k + 1] = 1;
dpL[0][0] = 1;
dpL[k + 1][n - 1] = 1;
dpR[0][0] = 1;
dpR[k + 1][n - 1] = 1;
for (int j = 1; j <= k; j++)
{
vector<int> pdp(n, -1);
for (int i = 0; i < n; i++)
{
if (i) pdp[i] = pdp[i - 1];
if (dpL[j - 1][i]) pdp[i] = i;
}
for (int i = 1; i < n; i++)
{
int L = i - c[j];
if (L < 0 || s[L] == 'X') continue;
if (cnt_[i] - cnt_[L] != 0) continue;
int a = prevX[L - 1];
int b = pdp[L - 1];
if (a <= b) dpL[j][i] = 1;
}
}
for (int j = k; j >= 1; j--)
{
vector<int> ndp(n, n);
for (int i = n - 1; i >= 0; i--)
{
if (i + 1 < n) ndp[i] = ndp[i + 1];
if (dpR[j + 1][i]) ndp[i] = i;
}
for (int i = n - 1; i >= 1; i--)
{
int R = i + c[j];
if (R >= n + 1 || s[R] == 'X') continue;
if (cnt_[R - 1] - cnt_[i - 1] != 0) continue;
int a = nextX[R + 1];
int b = ndp[R + 1];
if (b <= a) dpR[j][i] = 1;
for (int f = R + 1; f < n; f++)
{
if (dpR[j + 1][f])
{
dpR[j][i] = 1;
break;
}
if (s[f] == 'X') break;
}
}
}
// all below is O(nk)
vector<int> canX(s.size()), can_(s.size());
for (int j = 0; j < k + 2; j++)
{
for (int i = c[j] - 1; i < n; i++)
{
if (dpL[j][i] && dpR[j][i - c[j] + 1])
{
for (int p = i - c[j] + 1; p <= i; p++)
{
canX[p] = 1;
}
}
else
{
dpL[j][i] = 0;
dpR[j][i - c[j] + 1] = 0;
}
}
}
for (int i = 1; i < s.size(); i++)
{
if (s[i] == 'X') continue;
for (int j = 0; j < k + 2; j++)
{
if (dpL[j][i - 1]) dpL[j][i] = 1;
}
}
for (int i = s.size() - 2; i >= 0; i--)
{
if (s[i] == 'X') continue;
for (int j = 0; j < k + 2; j++)
{
if (dpR[j][i + 1]) dpR[j][i] = 1;
}
}
for (int i = 1; i < s.size() - 1; i++)
{
for (int j = 0; j + 1 < k + 2; j++)
{
if (dpL[j][i - 1] && dpR[j + 1][i + 1]) can_[i] = 1;
}
}
string ans = "";
for (int i = 2; i < s.size() - 2; i++)
{
if (!canX[i] && !can_[i]) exit(222);
if (s[i] != '.')
{
ans += s[i];
continue;
}
if (canX[i] && can_[i]) ans += "?";
if (!canX[i]) ans += "_";
if (!can_[i]) ans += "X";
}
return ans;
}
int main()
{
string s;
cin >> s;
int k;
cin >> k;
vector<int> c(k);
for (int i = 0; i < k; i++) cin >> c[i];
cout << solve_puzzle(s, c) << "\n";
}