| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 619960 | Dremix10 | 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 "paint.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
#ifdef dremix
#define p(x) cerr<<#x<<" = "<<x<<endl;
#define p2(x,y) cerr<<#x<<" , "<<#y<<" = "<<x<<" , "<<y<<endl;
#define pp(x) cerr<<#x<<" = "<<x.F<<"-"<<x.S<<endl;
#define pv(x) cerr<<#x<<" = {";for(auto v : x)cerr<<v<<", ";cerr<<"}"<<endl;
#define ppv(x) cerr<<#x<<" = {";for(auto v : x)cerr<<v.F<<"-"<<v.S<<", ";cerr<<"}"<<endl;
#else
#define p(x) {}
#define p2(x,y) {}
#define pp(x) {}
#define pv(x) {}
#define ppv(x) {}
#endif
const int N = 5001;
const int MOD = 1e9+7;
const ll INF = 1e18+5;
vector<vector<bool> > v;
vector<int> c,arr;
string s;
vector<int> prefw;
bool dp[N][N][N];
bool vis[N][N][N];
int cnt(int l, int r){
if(l == 0)return prefw[r];
return prefw[r] - prefw[l-1];
}
bool solve(int i, int j, int rem){
p2(i,j)
if(i == arr.size()){
assert(j == c.size() && rem == 0);
return true;
}
if(vis[i][j][rem])return dp[i][j][rem];
bool res = false;
if(arr[i] == 2 || arr[i] == 1){
if(j < c.size()){
bool ok = true;
if(cnt(i,i+c[j]-1) > 0)
ok = false;
if(arr[i+c[j]] == 1)
ok = false;
bool add = j + 1 < c.size();
bool p = false;
if(ok)
p = solve(i+c[j]+add,j+1,rem);
if(p){
for(int k=0;k<c[j];k++)
v[i+k][1] = true;
if(add)
v[i+c[j]][0] = true;
}
res |= p;
}
}
if(arr[i] == 2 || arr[i] == 0){
if(rem > 0){
bool p = solve(i+1,j,rem-1);
if(p){
v[i][0] = true;
}
res |= p;
}
}
dp[i][j][rem] = res;
vis[i][j][rem] = true;
return res;
}
std::string solve_puzzle(std::string S, std::vector<int> C) {
s = S;
c = C;
int n = s.size();
int m = c.size();
arr.resize(n);
int i,j;
for(i=0;i<n;i++){
if(s[i] == '_')
arr[i] = 0;
else if(s[i] == 'X')
arr[i] = 1;
else{
assert(s[i] == '.');
arr[i] = 2;
}
}
prefw.resize(n);
prefw[0] = arr[0] == 0;
for(i=1;i<n;i++){
prefw[i] = prefw[i-1] + (arr[i] == 0);
}
pv(arr)
pv(prefw)
int sum = 0;
for(auto x : c)
sum += x;
int gaps = n - sum;
assert(gaps >= m-1);
gaps -= m-1;
// there are (gaps + m) choose (m) ways to put the gaps
//rem = gaps;
v.assign(n,vector<bool>(2,false));
assert(solve(0,0,gaps));
string ans = "";
for(i=0;i<n;i++){
p(i)
p2(v[i][0],v[i][1])
if(v[i][0] == v[i][1]){
assert(v[i][0] != false);
ans += '?';
}
else if(v[i][0]){
ans += '_';
}
else{
ans += 'X';
}
}
return ans;
}