| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 828273 | caganyanmaz | Paint By Numbers (IOI16_paint) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "paint.h"
#define DEBUGGING
#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif
using namespace std;
constexpr static int INF = 1e9;
struct SegTree
{
vector<int> v;
int n;
SegTree(int n) : n(n), v(n*2, INF) {}
void build(const vector<int>& r) {
for (int i = n; i < 2*n; i++) v[i] = r[i-n];
for (int i = n-1; i > 0; i--) v[i] = min(v[i<<1], v[(i<<1)|1]);
}
int get(int l, int r)
{
int res = INF;
for (l+=n,r+=n;l<r;l>>=1,r>>=1)
{
if (l&1) res = min(res, v[l++]);
if (r&1) res = min(res, v[--r]);
}
return res;
}
};
#include <cstdlib>
string solve_puzzle(string s, vector<int> c)
{
vector<int> l(s.size()), r(s.size());
SegTree st(c.size());
st.build(c);
int cc = 0;
int cl = 0;
for (int i = 0; i < s.size(); i++)
{
if (cc == c.size())
{
l[i] = c.size()*2;
continue;
}
if (i - cl == c[cc])
{
for (int j = cl; j < i; j++)
l[j] = cc*2+1;
cc++;
l[i] = cc*2;
cl = i+1;
}
else if (s[i] == '_')
{
while (cl <= i)
l[cl++] = cc*2;
}
}
if (cc < c.size())
{
for (int j = cl; j < s.size(); j++)
l[j] = cc*2+1;
}
cc = c.size()-1;
int cr = s.size();
for (int i = s.size()-1; i >= 0; i--)
{
debug(i, cr, cc);
if (cc < 0)
{
r[i] = 0;
continue;
}
if (s[i] == '_')
{
while (cr > i)
r[--cr] = (cc+1) * 2;
}
else if (cr - i == c[cc])
{
for (int j = i; j < cr; j++)
r[j] = cc*2+1;
cc--;
if (i > 0) r[i-1] = (cc+1)*2;
cr = i-1;
i--;
}
}
vector<int> nlw(s.size());
vector<int> nrw(s.size());
int last = -1;
for (int i = 0; i < s.size(); i++)
{
if (s[i] == '_')
last = i;
nlw[i] = last;
}
last = s.size();
for (int i = s.size()-1; i >= 0; i--)
{
if (s[i] == '_')
last = i;
nrw[i] = last;
}
string res(s.size(), '?');
for (int i = 0; i < s.size(); i++)
{
if (l[i] != r[i])
{
int diff = nrw[i] - nlw[i];
if (l[i]&1 != r[i]&1)
continue;
debug(i, nlw[i], nrw[i], diff, r[i]/2, l[i]/2, st.get(r[i]/2, l[i]/2));
if (diff < st.get(r[i]/2, l[i]/2))
res[i] = '_';
}
else if (l[i]&1) res[i] = 'X';
else res[i] = '_';
}
debug(l,r);
return res;
}