| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1302782 | Mamikonm1 | Paint By Numbers (IOI16_paint) | C++17 | 1 ms | 348 KiB |
#include "paint.h"
#include <bits//stdc++.h>
using namespace std;
#define V vector
#define pb push_back
const int N=200;
std::string solve_puzzle(std::string s, std::vector<int> c) {
int n=s.size(),k=c.size();
V<bitset<N+1>>dp1(n),dp2(n);
dp1[0][0]=1;
dp2[n-1][0]=1;
V<int> mek(n);
string ans;
bool d,de,zro;
for(int i=0;i<n;++i){
if(i and s[i]!='X')dp1[i]|=dp1[i-1];
if(i and s[i-1]=='X')continue;
for(int j=0;j<k;++j){
d=0;
if(i<2)d=!j;
else d=dp1[i-2][j];
if(i+c[j]-1>=n or !d)continue;
if(i+c[j]<n and s[i+c[j]]=='X')continue;
dp1[i+c[j]-1][j+1]=1;
}
}
for(int i=n-1;i>=0;--i){
if(i+1<n and s[i]!='X')dp2[i]|=dp2[i+1];
if(i+1<n and s[i+1]=='X')continue;
for(int j=0;j<k;++j){
d=0;
if(i+2>=n)d=!j;
else d=dp2[i+2][j];
if(i-c[k-j-1]+1<0 or !d)continue;
if(i-c[k-j-1]>=0 and s[i-c[k-j-1]]=='X')continue;
dp2[i-c[k-j-1]+1][j+1]=1;
de=0;
if(i-c[k-j-1]-1<0)de=!(k-j-1);
else de=dp1[i-c[k-j-1]-1][k-j-1];
if(de){
mek[i-c[k-j-1]+1]++;
if(i+1<n)mek[i+1]--;
}
}
}
for(int i=0;i<n;++i){
if(s[i]!='.'){
ans.pb(s[i]);
continue;
}
if(i)mek[i]+=mek[i-1];
zro=0;
for(int j=0;j<=k;++j){
d=de=0;
if(!i)d=!j;
else d=dp1[i-1][j];
if(i==n-1)de=!(k-j);
else de=dp2[i+1][k-j];
if(d and de){
zro=1;
break;
}
}
if(zro and mek[i])ans.pb('?');
else if(zro)ans.pb('_');
else ans.pb('X');
assert(zro or mek[i]);
}
return ans;
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
