| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 774050 | PoonYaPat | Paint By Numbers (IOI16_paint) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}