QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#469062 | #6400. Game: Celeste | luanmenglei | WA | 0ms | 14072kb | C++14 | 2.6kb | 2024-07-09 12:30:32 | 2024-07-09 12:30:32 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
bool stB;
namespace SOL {
using i64 = long long;
using u64 = unsigned long long;
void debug(const char *msg, ...) {
#ifdef CLESIP
va_list arg;
static char pbString[512];
va_start(arg,msg);
vsprintf(pbString,msg,arg);
cerr << "[DEBUG] " << pbString << "\n";
va_end(arg);
#endif
}
template<typename T, typename L>
bool chkmax(T &x, L y) { if (x < y) return x = y, true; return false; }
template<typename T, typename L>
bool chkmin(T &x, L y) { if (y < x) return x = y, true; return false; }
const int N = 1e6 + 10;
const u64 B = 1313131;
int n, L, R, a[N], b[N];
bool vis[N];
u64 pw[N];
const int SEG_SIZE = N * 40;
u64 hsh[SEG_SIZE];
int rt[N], lc[SEG_SIZE], rc[SEG_SIZE], cnt[SEG_SIZE], tot;
void insert(int &x, int y, int l, int r, int p) {
x = ++ tot, lc[x] = lc[y], rc[x] = rc[y], hsh[x] = hsh[y] + pw[p], cnt[x] = cnt[y] + 1;
if (l == r) {
return;
}
int mid = (l + r) >> 1;
p <= mid ? insert(lc[x], lc[y], l, mid, p) : insert(rc[x], rc[y], mid + 1, r, p);
}
bool compare(int x, int y, int l, int r) {
if (l == r) {
return cnt[x] > cnt[y];
}
int mid = (l + r) >> 1;
if (hsh[rc[x]] == hsh[rc[y]])
return compare(lc[x], lc[y], l, mid);
else
return compare(rc[x], rc[y], mid + 1, r);
}
void work(int x, int l, int r) {
if (!x)
return;
if (l == r) {
for (int i = 1; i <= cnt[x]; i ++)
cout << l << " ";
return;
}
int mid = (l + r) >> 1;
work(rc[x], mid + 1, r);
work(lc[x], l, mid);
}
void ___solve() {
cin >> n >> L >> R;
pw[0] = 1;
for (int i = 1; i <= n; i ++)
pw[i] = pw[i - 1] * B;
tot = 0;
for (int i = 1; i <= n; i ++)
cin >> a[i], rt[i] = 0, vis[i] = 0;
for (int i = 1; i <= n; i ++)
cin >> b[i];
insert(rt[1], rt[0], 1, n, b[1]);
deque<int> dq;
for (int i = 2, j = 0; i <= n; i ++) {
while (j + 1 < i && a[i] - a[j + 1] >= L) {
j ++;
if (vis[j])
continue;
while (!dq.empty() && compare(rt[j], rt[dq.front()], 1, n))
dq.pop_front();
dq.push_front(j);
}
while (!dq.empty() && a[i] - a[dq.back()] > R)
dq.pop_back();
if (dq.empty()) {
vis[i] = 1;
} else {
insert(rt[i], rt[dq.back()], 1, n, b[i]);
}
}
if (vis[n]) {
cout << "-1\n";
} else {
work(rt[n], 1, n);
cout << "\n";
}
}
}
bool edB;
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int tt; cin >> tt;
while (tt --)
SOL::___solve();
#ifdef CLESIP
// cerr << "Time: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
// cerr << "Mem: " << (&stB - &edB) / 1024.0 / 1024.0 << "MB\n";
#endif
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 14072kb
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 '