| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 501427 | PoPularPlusPlus | Paint By Numbers (IOI16_paint) | C++17 | 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 <bits/stdc++.h>
//#include "paint.h"
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;
bool remender(ll a , ll b){return a%b;}
string solve_puzzle(string s , vector<int> c){
int n = s.size();
int k = c.size();
int pre[n];
if(s[0] == '_')pre[0] = 1;
else pre[0] = 0;
for(int i = 1; i < n; i++){
pre[i] = pre[i-1] + (s[i] == '_');
}
bool zero[n][k + 1] , one[n][k+1];;
memset(zero , 0 , sizeof zero);
memset(one,0,sizeof one);
if(s[0] != 'X')zero[0][0] = 1;
if(c[0] == 1){
if(s[0] != '_')one[0][1] = 1;
}
for(int i = 1; i < n; i++){
for(int j = 0; j <= k; j++){
if(s[i] == '_'){
zero[i][j] = max(zero[i-1][j] , one[i-1][j]);
}
else {
if(s[i] == 'X'){
if(j == 0){
continue;
}
if(c[j-1] <= i + 1){
if(c[j-1] == i + 1){
if(pre[i] == 0 && j == 1)one[i][j] = 1;
else one[i][j] = 0;
}
else {
int sum = pre[i] - pre[i - c[j-1]];
if(sum == 0)one[i][j] = zero[i - c[j-1]][j - 1];
}
}
else one[i][j] = 0;
}
else {
zero[i][j] = max(zero[i-1][j] , one[i-1][j]);
if(j != 0){
if(c[j-1] <= i + 1){
if(c[j-1] == i + 1){
if(pre[i] == 0 && j == 1){
one[i][j] = 1;
}
}
else {
int sum = pre[i] - pre[i - c[j-1]];
if(sum == 0){
one[i][j] = zero[i-c[j-1]][j-1];
}
}
}
}
}
}
}
}
string ans = "";
int cur = n - 1;
vector<pair<int,int>> v[n];
v[n-1].pb(mp(k,0));
v[n-1].pb(mp(k,1));
int last = n;
bool there[n][k + 1][2];
memset(there , 0 , sizeof there);
while(cur >= 0){
bool zero1 = 0 , one1 = 0;
for(auto i : v[cur]){
if(cur == 2 && i.vs == 1)cout << i.vf << '\n';
if(i.vs == 0){
zero1 = max(zero1 , zero[cur][i.vf]);
if(cur - 1 >= 0 && zero[cur][i.vf] == 1){
if(there[cur-1][i.vf][1] == 0){
v[cur-1].pb(mp(i.vf , 1));
there[cur-1][i.vf][1] = 1;
}
if(there[cur-1][i.vf][0] == 0){
v[cur-1].pb(mp(i.vf , 0));
there[cur - 1][i.vf][0] = 1;
}
}
continue;
}
one1 = max(one1 , one[cur][i.vf]);
if(one[cur][i.vf] == 1 && i.vf - 1 >= 0 && cur - c[i.vf-1] >= -1){
if(cur - c[i.vf-1] >= 0 && there[cur - c[i.vf-1]][i.vf-1][0] == 0){
v[cur - c[i.vf-1]].pb(mp(i.vf - 1 , 0));
there[cur - c[i.vf-1]][i.vf-1][0] = 1;
}
last = min(last , (cur - c[i.vf-1]) + 1);
}
}
if(last <= cur)one1 = 1;
if(one1 && zero1)ans += '?';
else if(one1)ans += 'X';
else ans += '_';
cur--;
}
reverse(all(ans));
return ans;
}
void solve(){
string s;
cin >> s;
int k;
cin >> k;
vector<int> v(k);
for(int i = 0; i < k; i++)cin >> v[i];
cout << solve_puzzle(s , v);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//freopen("dec.in", "r", stdin);
//freopen("dec.out", "w", stdout);
//int t;cin >> t;while(t--)
solve();
return 0;
}