| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 282305 | 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< int,int > 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 = 200002;
const lo mod = 1000000007;
int n,m,k,flag,t,PS[li];
int cev;
map<PII,int> dp,vis;
PII p[li];
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;
}
//~ cout<<dp[kac][sira]<<endl;
if(dp.find({sira,kac})!=dp.end())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 && (sira+c[kac]>=n || s[sira+c[kac]]!='X'))cevv=max(cevv,f(sira+c[kac]+1,kac+1,s,c));
}
else{
if(s[sira]!='_')if(kac<m)if(PS[sira+c[kac]-1]-(sira==0?0:PS[sira-1])==c[kac] && sira+c[kac]<=n && (sira+c[kac]>=n || s[sira+c[kac]]!='X'))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 ;
}
//~ cout<<vis[kac][sira]<<endl;
if(vis[{sira,kac}])return;
vis[{sira,kac}]=1;
if(s[sira]=='X'){
for(int i=sira;i<sira+c[kac];i++)p[i].se=1;
p[sira+c[kac]].fi=1;
yaz(sira+c[kac]+1,kac+1,s,c);
}
else if(s[sira]=='_'){
p[sira].fi=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] && (sira+c[kac]>=n || s[sira+c[kac]]!='X')){
for(int i=sira;i<sira+c[kac];i++)p[i].se=1;
p[sira+c[kac]].fi=1;
yaz(sira+c[kac]+1,kac+1,s,c);
}
}
if(kac==m && sira==n-1){
p[sira].fi=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] && (sira+c[kac]>=n || s[sira+c[kac]]!='X')){
for(int i=sira;i<sira+c[kac];i++)p[i].se=1;
p[sira+c[kac]].fi=1;
yaz(sira+c[kac]+1,kac+1,s,c);
}
}
}
if(sira+1<n){
if(s[sira]!='X'){
if(dp[{sira+1,kac}]==1){
p[sira].fi=1;
yaz(sira+1,kac,s,c);
}
}
}
}
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
//~ memset(dp,-1,sizeof(dp));
//~ dp.reset();
n=(int)s.size();
m=(int)c.size();
//~ for(int i=0;i<m;i++)dp[i].reset();
//~ for(int i=0;i<m;i++)vis[i].reset();
int say=0;
for(int i=0;i<(int)n;i++){
if(s[i]=='.')say++;
}
if(say==n && k*k+1000<=n){
for(int i=0;i<n;i++){ss+='?';}
return ss;
}
s+='0';
s+='0';
s+='0';
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(p[i].fi && p[i].se)ss+='?';
else if(p[i].fi)ss+='_';
else if(p[i].se)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;
}