# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1276397 | k12_khoi | Paint By Numbers (IOI16_paint) | C++17 | 0 ms | 0 KiB |
#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,k,c[N],sz[N];
bool f[N],g[N];
string s;
string solve_puzzle(string s,int c[])
{
string ans=s;
int k;
for (int i=0;i<=1000;i++)
if (c[i]==0)
{
k=i;
break;
}
int n=s.size();
string t=s;
function <void(int)> ql = [&] (int i) -> void
{
if (i==n)
{
int cur=0;
for (int i=0;i<n;i++)
sz[i]=0;
for (int i=0;i<n;i++)
{
if (t[i]=='_')
{
if (sz[cur]) cur++;
}
else sz[cur]++;
}
if (sz[cur]) cur++;
if (cur==k)
{
for (int i=0;i<k;i++)
if (c[i]!=sz[i]) return;
for (int i=0;i<n;i++)
if (t[i]=='X') f[i]=true;
else g[i]=true;
}
return;
}
if (s[i]=='.')
{
t[i]='X';
ql(i+1);
t[i]='_';
ql(i+1);
}
else ql(i+1);
};
ql(0);
for (int i=0;i<n;i++)
if (ans[i]=='.')
{
if (f[i] and g[i]) ans[i]='?';
else if (f[i]) ans[i]='X';
else ans[i]='_';
}
// auto sub4 = [&] ()
// {
// int cur;
//
// pre_W[0]=0;
// for (int i=1;i<=n;i++)
// pre_W[i]=pre_W[i-1]+(s[i-1]=='_');
//
// pre[0]=0;
// for (int i=1;i<=n;i++)
// {
// cur=pre[i-1];
// if (cur<k and i>=c[cur] and pre[i-c[cur]]==cur and pre_W[i]-(i-c[cur]>0 ? pre_W[i-c[cur]-1] : 0)==0)
// {
// cur++;
// f[i-cur]++;
// f[i+1]--;
// }
//
// pre[i]=cur;
// }
//
//
// suf[n+1]=k-1;
// for (int i=n;i>=1;i--)
// {
// cur=suf[i+1];
// if (cur>=0 and i+c[cur]<=n and suf[i+c[cur]]==cur and pre_W[i+c[cur]]-pre[i-1]==0) cur--;
//
// suf[i]=cur;
// }
//
// for (int i=1;i<=n;i++)
// {
// if (pre[i]<k and pos[pre[i]]==0) pos[pre[i]]=i;
// if (suf[i]>=0) last[suf[i]]=i;
// }
//
// for (int i=0;i<k;i++)
//
//
//
// return ans;
// }
return ans;
}