| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 607599 | APROHACK | 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 <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define ll long long
using namespace std;
ll k, n;
string str;
bool white[20005][2];
ll prefixed [20005], cuenta[20005];
ll mem[20005][105];
vector<ll>cs;
void llenar(ll dd, lldiv ht){
prefixed[dd]+=1;
prefixed[ht+1]+=-1;
}
bool dp(int position, int ci ){
if(ci==k && position == n)return true;
if(position >= n)return false;
if(mem[position][ci] != -1)return mem[position][ci];
//cout << " anali" << position << " " << ci << endl;
if(str[position]=='_'){
white[position][0]=true;
//cout << position << " " << ci << " " << dp(position+1, ci) << endl;
return mem[position][ci] = dp(position+1, ci);
}else if(str[position] != 'X'){ // .
bool ret = false;
if(dp(position+1, ci)){
white[position][0]=true;
ret = true;
}
bool posible = true;
if(ci==k){
//cout << position << " " << ci << " " << ret << endl;
return mem[position][ci] = ret ;
}
if(position+cs[ci]-1>=n)posible = false;
if(cuenta[position+cs[ci]-1] != cuenta[position])posible = false;
if(position+cs[ci] > n || str[position+cs[ci]] == 'X')posible = false;
if(posible && ((position+cs[ci] == n && ci == k-1) || dp(position+cs[ci]+1, ci+1))){
white[position][1]=true;
white[position+cs[ci]][0]=true;
llenar(position+1, position+cs[ci]-1);
//cout<< " nice "<< position << endl;
return mem[position][ci] = true;
}
//cout << position << " " << ci << " " << ret << endl;
return mem[position][ci] = ret ;
}else{
if(ci == k)return false;
bool posible = true;
if(position+cs[ci]-1>=n)return mem[position][ci] = false;
if(cuenta[position+cs[ci]-1] != cuenta[position])return mem[position][ci] = false;
if(position+cs[ci] > n || str[position+cs[ci]] == 'X')posible = false;
if(posible && ((position+cs[ci] == n && ci == k-1)||dp(position+cs[ci]+1, ci+1))){
white[position][1]=true;
white[position+cs[ci]][0]=true;
llenar(position+1, position+cs[ci]-1);
//cout << position << " " << ci << " " << true << endl;
return mem[position][ci] =true;
}
//cout << position << " " << ci << " " << false << endl;
return mem[position][ci] =false;
}
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
k=c.size(), n = s.size();
str = s;
for(int i = 0 ; i < k ; i ++)cs.pb(c[i]);
memset(white, false, sizeof white);
memset(mem, -1, sizeof mem);
ll cur = 0;
for(int i = 0 ; i < n ; i++){
if(str[i]=='_')cuenta[i]=++cur;
else cuenta[i]=cur;
}
for(int i = 0 ; i < n ; i ++)//cout << cuenta [i] << " ";
//cout << endl;
dp(0, 0);
string ans = "";
int pre = 0;
for(int i = 0 ; i < n ; i++){
pre+=prefixed[i];
//cout<<prefixed[i] << " ";
if(white[i][0] && (white[i][1] || pre > 0))ans+="?";
else if(white[i][0] )ans+="_";
else ans+= "X";
}
//cout << endl;
return ans;
}