| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 585433 | IvanJ | Paint By Numbers (IOI16_paint) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#include "paint.h"
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
int n, k;
int dp[maxn][105][2];
int cnt[maxn];
ll ans0[maxn], ans1[maxn];
vector<int> C;
string S;
int query(int x, int y) {
int ret = cnt[y];
if(x) ret -= cnt[x - 1];
return ret;
}
int rek(int pos, int x, int v) {
if(dp[pos][x][v] != -1)
return dp[pos][x][v];
if(pos > n) return 0;
if(pos == n) return (x == k);
int ret = 0;
if(v == 0) {
if(S[pos] != 'X')
ret = rek(pos + 1, x, 0) | rek(pos + 1, x, 1);
if(ret) ans0[pos]++, ans0[pos + 1]--;
} else {
if (x < k && query(pos, pos + C[x] - 1) == 0)
ret = rek(pos + C[x], x + 1, 0);
if(ret) ans1[pos]++, ans1[pos + C[x]]--;
}
return dp[pos][x][v] = ret;
}
string solve_puzzle(string s, vector<int> c) {
n = s.size(), k = c.size();
C = c, S = s;
cnt[0] = (s[0] == '_');
for(int i = 1;i < n;i++)
cnt[i] = cnt[i - 1] + (s[i] == '_');
memset(dp, -1, sizeof dp);
rek(0, 0, 0);
rek(0, 0, 1);
for(int i = 1;i < n;i++)
ans0[i] += ans0[i - 1], ans1[i] += ans1[i - 1];
string ret = "";
for(int i = 0;i < n;i++) {
if(s[i] != '.') ret += s[i];
else if(ans0[i] && ans1[i]) ret += "?";
else if(ans0[i]) ret += "_";
else if(ans1[i]) ret += "X";
else assert(1 != 1);
}
return ret;
}
int main() {
string s;
int K;
vector<int> v;
cin >> s >> K;
for(int i = 0;i < K;i++) {
int x;
cin >> x;
v.pb(x);
}
cout << solve_puzzle(s, v) << "\n";
return 0;
}