| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 434643 | Odavey | Paint By Numbers (IOI16_paint) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//
// ~oisín~ C++ Template
//
#include <bits/stdc++.h>
#define MX_N 5001
#define mp make_pair
#define mod7 1000000007
#define modpi 314159
#define PI 3.141592653589793238
#define pb push_back
#define FastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define All(a) a.begin(),a.end()
#define fi first
#define se second
#define ll long long int
#define ull unsigned long long int
int kx[8] = {+2, +2, -2, -2, +1, +1, -1, -1};
int ky[8] = {+1, -1, +1, -1, +2, -2, +2, -2};
int d9x[9] = {+1, +1, +1, +0, +0, +0, -1, -1, -1};
int d9y[9] = {+1, +0, -1, +1, +0, -1, +1, +0, -1};
int dx4[4] = {+0, +0, +1, -1};
int dy4[4] = {+1, -1, +0, +0};
ll gcd(ull a, ull b){
return (a==0)?b:gcd(b%a,a);
}
ll lcm(ull a, ull b){
return a*(b/gcd(a,b));
}
const long long INF = 1e18;
using namespace std;
string solve_puzzle(string& s, vector<int> c){
int n = s.size();
int k = c.size();
bool dp[n][k];
bool can[n][2];
int lowest[n][k];
int highest[n][k];
memset(dp, 0, sizeof(dp));
memset(can, 0, sizeof(can));
memset(lowest, -1, sizeof(lowest));
memset(highest, -1, sizeof(highest));
for(int w=0;w<k;++w){
for(int i=c[w]-1;i<n;++i){
bool no_room = false;
for(int j=i;j>=(i-c[w]+1);--j){
if(s[j] == '_'){
no_room = true;
break;
}
}
if(no_room){
continue;
}
if(w == 0){
bool impos = false;
for(int z=0;z<=i-c[w];++z){
if(s[z] == 'X'){
impos = true;
break;
}
}
if(impos != true){
dp[i][w] = true;
}
}else{
for(int j=0;j<i-c[w];++j){
bool impos = false;
for(int z=j+1;z<=i-c[w];++z){
if(s[z] == 'X'){
impos = true;
break;
}
}
if(dp[j][w-1] && impos != true){
dp[i][w] = true;
if(lowest[i][w] == -1){
lowest[i][w] = j;
}
highest[i][w] = j;
}
}
}
}
}
// for(int w=0;w<k;++w){
// for(int i=0;i<n;++i){
// cout << dp[i][w] << ' ';
// }
// cout << endl;
// }
int lo = 0, hi= n-1;
vector<int> candidates;
int highest_from[k+1];
memset(highest_from, -1, sizeof(highest_from));
highest_from[k] = n-1;
for(int w=k-1;~w;--w){
for(int i=lo;i<=hi;++i){
if(dp[i][w]){
candidates.pb(i);
highest_from[w] = i-c[w];
}
}
int x = candidates[0];
for(int j=x+1;j<=highest_from[w+1];++j){
can[j][0] = true;
}
lo = n, hi = -1;
for(int i : candidates){
lo = min(lo, lowest[i][w]);
hi = max(hi, highest[i][w]);
for(int j=i-c[w]+1;j<=i;++j){
can[j][1] = true;
}
}
candidates.clear();
}
for(int j=0;j<=highest_from[0];++j){
can[j][0] = true;
}
for(int i=0;i<n;++i){
if(s[i] != '.'){
continue;
}
if(can[i][0] && can[i][1]){
s[i] = '?';
}else if(can[i][1]){
s[i] = 'X';
}else{
s[i] = '_';
}
}
return s;
}