QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#135883 | #6400. Game: Celeste | kyEEcccccc | WA | 2ms | 9624kb | C++14 | 2.5kb | 2023-08-06 14:34:17 | 2023-08-06 14:34:18 |
Judging History
answer
// Author: kyEEcccccc
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
#define F(i, l, r) for (int i = (l); i <= (r); ++i)
#define FF(i, r, l) for (int i = (r); i >= (l); --i)
#define MAX(a, b) ((a) = max(a, b))
#define MIN(a, b) ((a) = min(a, b))
#define SZ(a) ((int)((a).size()) - 1)
constexpr int N = 1000005;
int n;
LL a[N], dl, dr;
int b[N];
namespace Case1
{
LL f[N], baka[N];
void solve(void)
{
f[n] = 1;
int cl = n, cr = n, cp = n + 1;
LL mx_l = LLONG_MIN / 2;
FF(i, n - 1, 1)
{
while (a[cl] - a[i] >= dl)
{
MAX(mx_l, f[cl]);
--cl;
}
while (a[cr] - a[i] > dr) --cr;
if (cr < cp)
{
mx_l = LLONG_MIN / 2;
cp = cl + 1;
baka[cl] = LLONG_MIN / 2;
F(i, cl + 1, cr) baka[i] = max(baka[i - 1], f[i]);
}
f[i] = max(mx_l, baka[cr]) + 1;
}
if (f[1] < 0) cout << "-1\n";
else
{
F(i, 1, f[1]) cout << 1 << ' ';
cout << '\n';
}
}
}
namespace Case2
{
bitset<10048> to[10048], baka[10048], tmp;
int ord[10048];
void solve(void)
{
to[n].reset();
to[n].set(n);
int cl = n, cr = n, cp = n + 1;
tmp.reset();
FF(i, n - 1, 1)
{
while (a[cr] - a[i] > dr) --cr;
while (a[cl] - a[i] >= dl)
{
if (cr >= cp) tmp |= to[cl];
--cl;
}
if (cr < cp)
{
tmp.reset();
cp = cl + 1;
baka[cl].reset();
F(i, cl + 1, cr) baka[i] = baka[i - 1] | to[i];
}
to[i] = tmp | baka[cr];
to[i].set(i);
}
if (!to[1].test(n)) return cout << "-1\n", void();
iota(ord + 1, ord + n + 1, 1);
sort(ord + 1, ord + n + 1, [] (int x, int y)
{ return b[x] > b[y]; });
set<LL> pos; multiset<int> val;
pos.insert(1), val.insert(-b[1]);
pos.insert(n), val.insert(-b[n]);
F(_, 1, n)
{
int i = ord[_];
if (i == 1 || i == n) continue;
int prv = *prev(pos.lower_bound(i)), nxt = *pos.upper_bound(i);
if (to[prv].test(i) && to[i].test(nxt))
{
pos.insert(i);
val.insert(-b[i]);
}
}
for (auto x : val) cout << -x << ' ';
cout << '\n';
}
}
void work(void)
{
cin >> n >> dl >> dr;
F(i, 1, n) cin >> a[i];
a[n + 1] = 10000000000LL;
bool all_1 = true;
F(i, 1, n)
{
cin >> b[i];
if (b[i] != 1) all_1 = false;
}
if (all_1) Case1::solve();
else Case2::solve();
}
signed main(void)
{
// freopen("jump.in", "r", stdin);
// freopen("jump.out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(nullptr);
int _; cin >> _;
while (_--) work();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 9624kb
input:
2 5 2 3 1 2 3 4 5 5 2 3 1 4 3 1 2 1 4 7 3 3 3
output:
5 4 3 -1
result:
wrong answer 1st lines differ - expected: '3', found: '5 4 3 '