| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 774050 | PoonYaPat | Paint By Numbers (IOI16_paint) | C++14 | 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.
#include "paint.h"
#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
struct node {
int n,k,mode;
};
int n,m,bef[200010],mark[200010];
bool dp[200010][110][2],canX[200010],canY[200010];
string ans;
vector<node> adj[200010][110][2];
bool vis[200010][110][2];
string solve_puzzle(string s, vector<int> c) {
n=s.size();
m=c.size();
int before=0;
s=" "+s;
for (int i=1; i<=n; ++i) {
if (s[i]=='_') before=i;
bef[i]=before;
}
dp[0][0][0]=true;
for (int i=1; i<=n; ++i) {
for (int j=0; j<=m; ++j) {
if (s[i]!='X') {
if (dp[i-1][j][0]) {
dp[i][j][0]=true;
adj[i][j][0].push_back({i-1,j,0});
}
if (j && dp[i-1][j-1][1]) {
dp[i][j][0]=true;
adj[i][j][0].push_back({i-1,j-1,1});
}
}
if (s[i]!='_') {
if (i-bef[i]>=c[j] && i>=c[j] && dp[i-c[j]][j][0] && j<m) {
dp[i][j][1]=true;
adj[i][j][1].push_back({i-c[j],j,0});
}
}
}
}
/*
queue<node> q;
if (dp[n][m][0]) q.push({n,m,0});
if (dp[n][m-1][1]) q.push({n,m-1,1});
int cnt=0;
while (!q.empty()) {
int a=q.front().n, b=q.front().k, mode=q.front().mode;
assert(++cnt<=10000000);
q.pop();
if (vis[a][b][mode]) continue;
vis[a][b][mode]=true;
if (mode==0) canY[a]=true;
if (mode==1) ++mark[a-c[b]+1], --mark[a+1];
for (auto s : adj[a][b][mode]) q.push(s);
}
for (int i=1; i<=n; ++i) {
mark[i]+=mark[i-1];
if (mark[i]) canX[i]=true;
} */
for (int i=1; i<=n; ++i) {
if (s[i]=='X') ans+='X';
else if (s[i]=='Y') ans+='Y';
else {
if (canX[i] && canY[i]) ans+='?';
else if (canX[i]) ans+='X';
else if (canY[i]) ans+='_';
}
}
return ans;
}