| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 282262 | AKaan37 | Paint By Numbers (IOI16_paint) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//Bismillahirrahmanirrahim
//~ #include "paint.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long lo;
typedef pair< lo,lo > PII;
#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
const lo inf = 1000000000000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 200005;
const lo mod = 1000000007;
int n,m,b[li],a[li],k,flag,t,PS[li],beyaz[li],siyah[li],dp[li][105],vis[li][105];
int cev;
string ss;
inline int f(int sira,int kac,std::string s,vector<int> c){
int cevv=0;
if(sira>=n){
if(kac==m)return 1;
return 0;
}
if(~dp[sira][kac])return dp[sira][kac];
if(s[sira]=='X'){
if(kac<m)if(PS[sira+c[kac]-1]-(sira==0?0:PS[sira-1])==c[kac] && sira+c[kac]<=n)cevv=max(cevv,f(sira+c[kac]+1,kac+1,s,c));
}
else{
if(kac<m)if(PS[sira+c[kac]-1]-(sira==0?0:PS[sira-1])==c[kac] && sira+c[kac]<=n)cevv=max(cevv,f(sira+c[kac]+1,kac+1,s,c));
cevv=max(cevv,f(sira+1,kac,s,c));
}
return dp[sira][kac]=cevv;
}
inline void yaz(int sira,int kac,string s,vector<int> c){
//~ cout<<sira<<" : : "<<kac<<endl;
if(sira>=n){
return ;
}
if(vis[sira][kac])return;
vis[sira][kac]=1;
if(s[sira]=='X'){
for(int i=sira;i<sira+c[kac];i++)siyah[i]=1;
beyaz[sira+c[kac]]=1;
yaz(sira+c[kac]+1,kac+1,s,c);
}
else if(s[sira]=='_'){
beyaz[sira]=1;
yaz(sira+1,kac,s,c);
}
else{
if(kac<m){
if(sira+c[kac]+1>=n && PS[sira+c[kac]-1]-(sira==0?0:PS[sira-1])==c[kac]){
for(int i=sira;i<sira+c[kac];i++)siyah[i]=1;
beyaz[sira+c[kac]]=1;
yaz(sira+c[kac]+1,kac+1,s,c);
}
}
if(kac==m && sira==n-1){
beyaz[sira]=1;
yaz(sira+1,kac,s,c);
}
if(kac<m){
if(sira+c[kac]+1<n){
if(dp[sira+c[kac]+1][kac+1]==1 && PS[sira+c[kac]-1]-(sira==0?0:PS[sira-1])==c[kac]){
for(int i=sira;i<sira+c[kac];i++)siyah[i]=1;
beyaz[sira+c[kac]]=1;
yaz(sira+c[kac]+1,kac+1,s,c);
}
}
}
if(sira+1<n){
if(s[sira]!='X'){
if(dp[sira+1][kac]==1){
beyaz[sira]=1;
yaz(sira+1,kac,s,c);
}
}
}
}
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
memset(dp,-1,sizeof(dp));
n=(int)s.size();
m=(int)c.size();
for(int i=0;i<n;i++){
if(i==0){
if(s[i]!='_')PS[i]=1;
continue;
}
PS[i]=PS[i-1];
if(s[i]!='_')PS[i]++;
}
PS[n]=PS[n-1];
PS[n+1]=PS[n-1];
PS[n+2]=PS[n-1];
f(0,0,s,c);
yaz(0,0,s,c);
for(int i=0;i<n;i++){
if(s[i]=='X')ss+='X';
else if(s[i]=='_')ss+='_';
else if(beyaz[i] && siyah[i])ss+='?';
else if(beyaz[i])ss+='_';
else if(siyah[i])ss+='X';
}
//~ cout<<"**\n";
//~ cout<<ss.size()<<endl;
return ss;
}
const int S_MAX_LEN = 200 * 1000;
char buf[S_MAX_LEN + 1];
int main() {
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;
}