# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
288690 | IgorI | Paint By Numbers (IOI16_paint) | C++17 | 1 ms | 896 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define forn(i, n) for (int (i) = 0; (i) < (n); (i)++)
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long ll;
const int N = 200007;
const int K = 103;
int dpL[K][N];
int dpR[K][N];
string solve_puzzle(string s, vector<int> c)
{
s = "X." + s + ".X";
int k = c.size();
c.push_back(1);
reverse(all(c));
c.push_back(1);
reverse(all(c));
int n = s.size();
c[0] = 1, c[k + 1] = 1;
dpL[0][0] = 1;
dpR[k + 1][n - 1] = 1;
for (int j = 1; j <= k; j++)
{
for (int i = 1; i < n; i++)
{
if (j == k)
{
int t = 1;
for (int p = i + 1; p < n - 1; p++) if (s[p] == 'X') t = 0;
if (!t) continue;
}
int L = i - c[j];
if (L < 0 || s[L] == 'X') continue;
int t = 1;
for (int f = L + 1; f <= i; f++)
{
if (s[f] == '_')
{
t = 0;
break;
}
}
if (!t) continue;
for (int f = L - 1; f >= 0; f--)
{
if (dpL[j - 1][f])
{
dpL[j][i] = 1;
break;
}
if (s[f] == 'X') break;
}
}
}
for (int j = k; j >= 1; j--)
{
for (int i = n - 1; i >= 1; i--)
{
if (j == 1)
{
int t = 1;
for (int p = i - 1; p > 0; p--) if (s[p] == 'X') t = 0;
if (!t) continue;
}
int R = i + c[j];
if (R >= n + 1 || s[R] == 'X') continue;
int t = 1;
for (int f = i; f < R; f++)
{
if (s[f] == '_')
{
t = 0;
break;
}
}
if (!t) continue;
for (int f = R + 1; f < n; f++)
{
if (dpR[j + 1][f])
{
dpR[j][i] = 1;
break;
}
if (s[f] == 'X') break;
}
}
}
vector<int> canX(s.size()), can_(s.size());
for (int j = 1; j < k + 1; j++)
{
for (int i = c[j] - 1; i < n; i++)
{
if (dpL[j][i] && dpR[j][i - c[j] + 1])
{
for (int p = i - c[j] + 1; p <= i; p++)
{
canX[p] = 1;
}
}
else
{
dpL[j][i] = 0;
dpR[j][i - c[j] + 1] = 0;
}
}
}
for (int i = 1; i < s.size(); i++)
{
for (int j = 0; j < k + 2; j++)
{
if (dpL[j][i - 1]) dpL[j][i] = 1;
}
}
for (int i = s.size() - 2; i >= 0; i--)
{
for (int j = 0; j < k + 2; j++)
{
if (dpR[j][i + 1]) dpR[j][i] = 1;
}
}
for (int i = 1; i < s.size() - 1; i++)
{
for (int j = 0; j + 1 < k + 2; j++)
{
if (dpL[j][i - 1] && dpR[j + 1][i + 1]) can_[i] = 1;
}
}
string ans = "";
for (int i = 2; i < s.size() - 2; i++)
{
if (!canX[i] && !can_[i]) exit(222);
if (s[i] != '.')
{
ans += s[i];
continue;
}
if (canX[i] && can_[i]) ans += "?";
if (!canX[i]) ans += "_";
if (!can_[i]) ans += "X";
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |