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