| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 712550 | neki | Paint By Numbers (IOI16_paint) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int mn = 200100;
const int mk = 110;
bool dl[mk][mn], dr[mk][mn];
int ps[mn], cX[mn], c_[mn];
string solve_puzzle(std::string s, std::vector<int> c)
{
const int n = s.size(), k = c.size();
for (int i = n - 1; i >= 0; --i)
ps[i] = ps[i + 1] + (s[i] == '_');
for (int b = 0; b < k; ++b)
{
bool can = 0;
for (int i = 0; i < n; ++i)
if (i - c[b] + 1 >= 0)
{
if (b == 0)
{
if (i - c[b] >= 0 && s[i - c[b]] == 'X')
break;
if (ps[i - c[b] + 1] - ps[i + 1] == 0)
dl[b][i] = 1;
}
else if (i - c[b] - 1 >= 0)
{
if (s[i - c[b]] == 'X')
can = 0;
if (s[i - c[b]] != 'X' && dl[b - 1][i - c[b] - 1])
can = 1;
if (can && ps[i - c[b] + 1] - ps[i + 1] == 0)
dl[b][i] = 1;
}
}
}
for (int b = k - 1; b >= 0; --b)
{
bool can = 0;
for (int i = n - 1; i >= 0; --i)
if (i + c[b] - 1 < n)
{
if (b == k - 1)
{
if (i + c[b] < n && s[i + c[b]] == 'X')
break;
if (ps[i] - ps[i + c[b]] == 0)
dr[b][i] = 1;
}
else if (i + c[b] + 1 >= 0)
{
if (s[i + c[b]] == 'X')
can = 0;
if (s[i + c[b]] != 'X' && dr[b + 1][i + c[b] + 1])
can = 1;
if (can && ps[i] - ps[i + c[b]] == 0)
dr[b][i] = 1;
}
}
}
/*cout << "k:" << k << endl;
for (int b = 0; b < k; ++b)
{
cout << b << ": " << endl;
for (int i = 0; i < n; ++i)
cout << dr[b][i] << " ";
cout << endl;
}*/
for (int b = 0; b < k; ++b)
for (int i = 0; i < n; ++i)
if (i - c[b] + 1 >= 0 && dl[b][i] && dr[b][i - c[b] + 1])
++cX[i - c[b] + 1], --cX[i + 1];
for (int i = 1; i < n; ++i)
cX[i] += cX[i - 1];
for (int b = 0; b < k; ++b)
{
for (int i = 0; i < n; ++i)
{
if (s[i] != 'X' && i && dl[b][i - 1])
dl[b][i] = 1;
}
for (int i = n - 1; i >= 0; --i)
{
if (s[i] != 'X' && i + 1 < n && dr[b][i + 1])
dr[b][i] = 1;
}
for(int b = 0; b < k; ++b)
{
for (int i = 0; i < n; ++i)
if (b + 1 < k && i - 1 >= 0 && i + 1 < n && dl[b][i - 1] && dr[b + 1][i + 1] && s[i] != 'X')
++c_[i];
}
for (int i = n - 1; i >= 0; --i)
{
if (s[i] == 'X')
break;
if (i - 1 >= 0 && dl[k - 1][i - 1])
++c_[i];
}
for (int i = 0; i < n; ++i)
{
if (s[i] == 'X')
break;
if (i + 1 < n && dr[0][i + 1])
++c_[i];
}
string ans(n, '.');
for (int i = 0; i < n; ++i)
ans[i] = (cX[i] && c_[i] ? '?' : cX[i] ? 'X'
: '_');
return ans;
}