| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 705050 | esomer | Paint By Numbers (IOI16_paint) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "paint.h"
using namespace std;
#define endl "\n"
typedef long long int ll;
const int MOD = 1e9 + 7;
string solve_puzzle(string s, vector<int> c){
int n = (int)s.size();
int k = (int)c.size();
vector<vector<int>> left(n, vector<int>(k, 0));
int mn = n;
int mx = -1;
int lst = -1;
for(int i = 0; i < n; i++){
if(s[i] == 'X'){mn = min(mn, i); mx = i;}
if(s[i] != 'X' && i > 0){
for(int j = 0; j < k; j++){
if(left[i-1][j] != 0) left[i][j] = 1;
}
}
if(s[i] == '_') {lst = i; continue;}
for(int j = 0; j < k; j++){
if(lst >= i - c[j] + 1) continue;
if(i - c[j] < 0 || s[i - c[j]] != 'X'){
if(j == 0){
if(mn > i - c[j]) left[i][j] = 2;
}else if(i - c[j] - 1 >= 0 && left[i - c[j] - 1][j-1] > 0) left[i][j] = 2;
}
}
}
vector<vector<int>> right(n, vector<int>(k, 0));
lst = n;
vector<int> v;
for(int i = n - 1; i >= 0; i--){
if(s[i] != 'X' && i < n - 1){
for(int j = 0; j < k; j++){
if(right[i+1][j] != 0) right[i][j] = 1;
}
}
if(s[i] == '_') {v.push_back(i); lst = i; continue;}
for(int j = 0; j < k; j++){
if(lst <= i + c[j] - 1) continue;
if(i + c[j] >= n || s[i + c[j]] != 'X'){
if(j == k-1){
if(mx <= i + c[j]) right[i][j] = 2;
}else if(i + c[j] + 1 < n && right[i + c[j] + 1][j+1] > 0) right[i][j] = 2;
}
}
}
vector<int> next(n, -1);
for(int i = 0; i < n; i++){
if(s[i] == '_') {v.pop_back(); continue;}
int mex = -1;
for(int j = 0; j < k; j++){
if(i + c[j] - 1 >= n || ((int)v.size() > 0 && v.back() <= i + c[j] - 1) || (i > 0 && s[i-1] == 'X') || (i == 0 && j > 0)) continue;
bool gd = 0;
if(j == 0){
if(mn >= i){
if(k == 1){
if(i + c[j] >= n || s[i + c[j]] != 'X') gd = 1;
}else{
if(i + c[j] + 1 < n && s[i + c[j]] != 'X' && right[i + c[j] + 1][j+1] > 0) gd = 1;
}
}
}else if(j == k - 1){
if(mx <= i + c[j] - 1){
if(left[i-1][j-1] > 0) gd = 1;
}
}else{
if(left[i-1][j-1] > 0 && i + c[j] + 1 < n && s[i + c[j]] != 'X' && right[i + c[j] + 1][j+1] > 0) gd = 1;
}
if(gd) mex = max(mex, i + c[j] - 1);
}
next[i] = mex;
}
//~ cout << "mx " << mx << " mn " << mn << endl;
//~ for(int i = 0; i < n; i++){
//~ cout << "I: " << i << endl;
//~ for(int j = 0; j < k; j++){
//~ cout << "J " << j << " left " << left[i][j] << " right " << right[i][j] << endl;
//~ }
//~ }
vector<int> er(n, 0);
int curr = 0;
string ans = s;
for(int i = 0; i < n; i++){
if(next[i] != -1){
curr++;
er[next[i]]++;
}
if(i > 0) curr -= er[i-1];
if(ans[i] == '.'){
bool white = 0;
if((i < n - 1 && right[i+1][0] > 0 && mn > i) || (i > 0 && left[i-1][k-1] > 0 && mx < i)) white = 1;
if(i > 0 && i < n - 1){
for(int j = 0; j < k - 1; j++){
if(left[i-1][j] > 0 && right[i+1][j+1] > 0) white = 1;
}
}
if(!white){
ans[i] = 'X';
continue;
}
if(curr > 0) ans[i] = '?';
else ans[i] = '_';
}
}
return ans;
}
//~ const int S_MAX_LEN = 200 * 1000;
//~ char buf[S_MAX_LEN + 1];
//~ int main() {
//~ assert(1 == scanf("%s", buf));
//~ std::string s = buf;
//~ int c_len;
//~ assert(1 == scanf("%d", &c_len));
//~ std::vector<int> c(c_len);
//~ for (int i = 0; i < c_len; i++) {
//~ assert(1 == scanf("%d", &c[i]));
//~ }
//~ std::string ans = solve_puzzle(s, c);
//~ printf("%s\n", ans.data());
//~ return 0;
}