| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 592239 | Elias | Paint By Numbers (IOI16_paint) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
int n, k;
vector<bool> hi;
vector<int> cl;
unordered_map<int, bool> dp;
vector<int> wh, bl;
vector<int> numWhite;
bool checkWhite(int l, int r)
{
int cnt = numWhite[r - 1];
if (l)
cnt -= numWhite[l - 1];
return cnt;
}
bool DP(int i, int j)
{
if (i <= 0)
return j == 0;
if (dp.count(i + (j << 20)))
return dp[i + (j << 20)];
bool b = false;
if (j > 0)
{
int size = cl[j - 1];
if (i >= size && (i == size || !hi[i - size - 1]) && !checkWhite(i - size, i))
{
if (DP(i - size - 1, j - 1))
{
b = true;
if (i != n)
bl[i]--;
bl[i - size]++;
if (i - size > 0)
wh[i - size - 1]++;
}
}
}
if (!hi[i - 1])
{
if (DP(i - 1, j))
{
b = true;
wh[i - 1]++;
}
}
return dp[i + (j << 20)] = b;
}
string solve_puzzle(string s, vector<int> c)
{
n = s.size();
k = c.size();
cl = c;
hi = vector<bool>(n);
numWhite = vector<int>(n);
for (int i = 0; i < n; i++)
{
numWhite[i] += numWhite[max(i - 1, 0)];
if (s[i] == 'X')
hi[i] = true;
if (s[i] == '_')
numWhite[i]++;
}
wh = bl = vector<int>(n);
DP(n, k);
int black = 0;
string out;
for (int i = 0; i < n; i++)
{
black += bl[i];
if (black && wh[i])
out.push_back('?');
else if (black)
out.push_back('X');
else
out.push_back('_');
}
return out;
}
signed main()
{
cin.tie(0);
ios_base::sync_with_stdio(false);
int n, k;
cin >> n >> k;
string s;
cin >> s;
vector<int> blub(k);
for (int &x : blub)
cin >> x;
cout << solve_puzzle(s, blub);
}