Submission #774041

#TimeUsernameProblemLanguageResultExecution timeMemory
774041PoonYaPatPaint By Numbers (IOI16_paint)C++14
0 / 100
239 ms524288 KiB
#include "paint.h" #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}); while (!q.empty()) { int a=q.front().n, b=q.front().k, mode=q.front().mode; 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...