# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1268397 | kl0989e | Paint By Numbers (IOI16_paint) | C++20 | 0 ms | 0 KiB |
#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pi pair<int, int>
#define pl pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
string solve_puzzle(string s, vi c) {
int n=s.size();
int k=c.size();
for (int i=0; i<n; i++) {
if (s[i]=='.') {
s[i]='?';
}
}
vector<vi> dp(n+1,vi(k+1,0));
dp[0][0]=1;
for (int i=1; i<=n; i++) {
for (int j=0; j<=k; j++) {
if (s[i-1]!='X') {
dp[i][j]|=dp[i-1][j];
}
if (j>0 && c[j-1]>=i && count(s.begin()+i-c[j-1],s.begin()+i,'_')==0 && (i-c[j-1]-1<0 || s[i-c[j-1]-1]!='X')) {
dp[i][j]|=(dp[max(i-c[j-1]-2,0)][j-1]);
}
}
}
reverse(all(s));
reverse(all(c));
vector<vi> dp1(n+1,vi(k+1,0));
dp1[0][0]=1;
for (int i=1; i<n; i++) {
for (int j=0; j<=k; j++) {
if (s[i-1]!='X') {
dp[i][j]|=dp[i-1][j];
}
if (j>0 && c[j-1]>=i && count(s.begin()+i-c[j-1],s.begin()+i,'_')==0 && (i-c[j-1]-1<0 || s[i-c[j-1]-1]!='X')) {
dp[i][j]|=(dp[max(i-c[j-1]-2,0)][j-1]);
}
}
}
reverse(all(s));
reverse(all(c));
int mx=-1;
for (int i=0; i<n; i++) {
if (s[i]!='?') {
continue;
}
bool a=0,b=0;
for (int j=0; j<=k; j++) {
a|=dp[i][j]&dp[n-i-1][k-j];
if ((i==0 || (dp[i-1][j] && s[i-1]!='X')) && (n-i-c[j]-1<0 || (dp[n-i-c[j]-1][k-j-1] && s[i+c[j]]!='X')) && i+c[j]<=n && ) {
}
}
if (a && b) {
s[i]='?';
}
else if (a) {
s[i]='_';
}
else if (b) {
s[i]='X';
}
}
return s;
}