| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 69823 | evpipis | Paint By Numbers (IOI16_paint) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define TEST
const int len = 2e5+5;
int pref[len], n, k, white[len], black[len];
bool dp1[len][105][2], dp2[len][105][2];
char str[len];
int sz[len];
bool can(int l, int r){
return (1 <= l && r <= n && pref[r]-pref[l-1] == 0);
}
string solve_puzzle(string S, vector<int> C) {
n = S.size(), k = C.size();
for (int i = 1; i <= k; i++)
sz[i] = C[i-1];
for (int i = 1; i <= n; i++)
str[i] = S[i-1];
for (int i = 1; i <= n; i++){
pref[i] = pref[i-1];
if (str[i] == '_')
pref[i]++;
}
for (int i = n+1; i >= 1; i--)
for (int j = 1; j <= k+1; j++)
for (int t = 0; t < 2; t++){
if (i == n+1 && j == k+1){
dp1[i][j][t] = true;
continue;
}
if ((j == k+1 && t == 1) || (i == n+1)){
dp1[i][j][t] = false;
continue;
}
bool ans = false;
if (t == 0){
if (str[i] != 'X')
ans = dp1[i+1][j][0]|dp1[i+1][j][1];
}
else{
if (str[i] != '_' && can(i, i+sz[j]-1))
ans = dp1[i+sz[j]][j+1][0];
}
dp1[i][j][t] = ans;
}
for (int i = 0; i <= n; i++)
for (int j = 0; j <= k; j++)
for (int t = 0; t < 2; t++){
if (i == 0 && j == 0){
dp2[i][j][t] = true;
continue;
}
if ((j == 0 && t == 1) || (i == 0)){
dp2[i][j][t] = false;
continue;
}
bool ans = false;
if (t == 0){
if (str[i] != 'X')
ans = dp2[i-1][j][0]|dp2[i-1][j][1];
}
else{
if (str[i] != '_' && can(i-sz[j]+1, i))
ans = dp2[i-sz[j]][j-1][0];
}
dp2[i][j][t] = ans;
}
//printf("fine till here\n"), fflush(stdout);
string out;
out.resize(n);
for (int i = 1; i <= n; i++){
for (int j = 1; j <= k+1; j++){
//printf("i = %d, j = %d\n", i, j), fflush(stdout);
if (dp1[i][j][0] && (dp2[i-1][j-1][1]|dp2[i-1][j-1][0]))
white[i] = 1;
//printf("fir\n"), fflush(stdout);
if (dp1[i][j][1] && dp2[i-1][j-1][0])
black[i]++, black[i+sz[j]]--;
//printf("sec\n"), fflush(stdout);
}
}
for (int i = 1; i <= n; i++)
black[i] += black[i-1];
for (int i = 1; i <= n; i++){
if (str[i] != '.')
out[i-1] = str[i];
else if (black[i] && white[i])
out[i-1] = '?';
else if (black[i])
out[i-1] = 'X';
else
out[i-1] = '_';
}
//for (int i = 1; i <= n; i++)
// printf("%d ", rig(i, 1, 1));
//printf("\n");
return out;
}
#ifdef TEST
const int S_MAX_LEN = 200 * 1000;
char buf[S_MAX_LEN + 1];
int main() {
freopen("04", "r", stdin);
assert(1 == scanf("%s", buf));
std::string s = buf;
int c_len;
assert(1 == scanf("%d", &c_len));
std::vector<int> c(c_len);
for (int i = 0; i < c_len; i++) {
assert(1 == scanf("%d", &c[i]));
}
std::string ans = solve_puzzle(s, c);
printf("%s\n", ans.data());
return 0;
}
#endif