QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#104131 | #6400. Game: Celeste | hos_lyric | WA | 236ms | 3820kb | C++14 | 7.5kb | 2023-05-09 01:42:17 | 2023-05-09 01:42:58 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
////////////////////////////////////////////////////////////////////////////////
// 2^61 - 1 = 2'305'843'009'213'693'951
struct ModLong61 {
static constexpr unsigned long long M = (1ULL << 61) - 1;
unsigned long long x;
ModLong61() : x(0ULL) {}
ModLong61(unsigned x_) : x(x_ % M) {}
ModLong61(unsigned long long x_) : x(x_ % M) {}
ModLong61(int x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
ModLong61(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
ModLong61 &operator+=(const ModLong61 &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
ModLong61 &operator-=(const ModLong61 &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
ModLong61 &operator*=(const ModLong61 &a) {
const unsigned __int128 y = static_cast<unsigned __int128>(x) * a.x;
x = (y >> 61) + (y & M);
x = (x >= M) ? (x - M) : x;
return *this;
}
ModLong61 &operator/=(const ModLong61 &a) { return (*this *= a.inv()); }
ModLong61 pow(long long e) const {
if (e < 0) return inv().pow(-e);
ModLong61 a = *this, b = 1ULL; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
}
ModLong61 inv() const {
unsigned long long a = M, b = x; long long y = 0, z = 1;
for (; b; ) { const unsigned long long q = a / b; const unsigned long long c = a - q * b; a = b; b = c; const long long w = y - static_cast<long long>(q) * z; y = z; z = w; }
assert(a == 1ULL); return ModLong61(y);
}
ModLong61 operator+() const { return *this; }
ModLong61 operator-() const { ModLong61 a; a.x = x ? (M - x) : 0ULL; return a; }
ModLong61 operator+(const ModLong61 &a) const { return (ModLong61(*this) += a); }
ModLong61 operator-(const ModLong61 &a) const { return (ModLong61(*this) -= a); }
ModLong61 operator*(const ModLong61 &a) const { return (ModLong61(*this) *= a); }
ModLong61 operator/(const ModLong61 &a) const { return (ModLong61(*this) /= a); }
template <class T> friend ModLong61 operator+(T a, const ModLong61 &b) { return (ModLong61(a) += b); }
template <class T> friend ModLong61 operator-(T a, const ModLong61 &b) { return (ModLong61(a) -= b); }
template <class T> friend ModLong61 operator*(T a, const ModLong61 &b) { return (ModLong61(a) *= b); }
template <class T> friend ModLong61 operator/(T a, const ModLong61 &b) { return (ModLong61(a) /= b); }
explicit operator bool() const { return x; }
bool operator==(const ModLong61 &a) const { return (x == a.x); }
bool operator!=(const ModLong61 &a) const { return (x != a.x); }
friend std::ostream &operator<<(std::ostream &os, const ModLong61 &a) { return os << a.x; }
};
////////////////////////////////////////////////////////////////////////////////
#include <chrono>
#include <random>
// [l, r]
Int randLong(Int l, Int r) {
static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
return uniform_int_distribution<Int>(l, r)(rng);
}
const ModLong61 BASE = randLong(0, ModLong61::M - 1);
////////////////////////////////////////////////////////////////////////////////
int N;
Int L, R;
vector<Int> X;
vector<int> A;
int E;
vector<ModLong61> BB;
struct Node {
int l, r;
ModLong61 h;
};
int nodesLen;
vector<Node> nodes;
int newLeaf(ModLong61 h) {
const int u = nodesLen++;
nodes[u].l = -1;
nodes[u].r = -1;
nodes[u].h = h;
return u;
}
int newInternal(int e, int l, int r) {
const int u = nodesLen++;
nodes[u].l = l;
nodes[u].r = r;
nodes[u].h = nodes[l].h + BB[e - 1] * nodes[r].h;
return u;
}
int cmp(int u, int v) {
for (int e = E; --e >= 0; ) {
if (nodes[nodes[u].r].h != nodes[nodes[v].r].h) {
u = nodes[u].r;
v = nodes[v].r;
} else {
u = nodes[u].l;
v = nodes[v].l;
}
}
return (nodes[u].h.x > nodes[v].h.x) ? +1 : (nodes[u].h.x < nodes[v].h.x) ? -1 : 0;
}
int incr(int e, int u, int pos) {
if (e == 0) {
return newLeaf(nodes[u].h + 1);
} else {
if (pos >> (e - 1) & 1) {
return newInternal(e, nodes[u].l, incr(e - 1, nodes[u].r, pos));
} else {
return newInternal(e, incr(e - 1, nodes[u].l, pos), nodes[u].r);
}
}
}
int incr(int u, int pos) {
return incr(E, u, pos);
}
void dfs(int e, int a, int u, vector<int> &as) {
if (!nodes[u].h) return;
if (e == 0) {
for (int i = 0; i < (int)nodes[u].h.x; ++i) {
as.push_back(a);
}
} else {
dfs(e - 1, a | 1 << (e - 1), nodes[u].r, as);
dfs(e - 1, a , nodes[u].l, as);
}
}
void dfs(int u, vector<int> &as) {
dfs(E, 0, u, as);
}
int main() {
for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
scanf("%d%lld%lld", &N, &L, &R);
X.resize(N);
for (int i = 0; i < N; ++i) {
scanf("%lld", &X[i]);
}
A.resize(N);
for (int i = 0; i < N; ++i) {
scanf("%d", &A[i]);
}
for (E = 0; !(N < 1 << E); ++E) {}
BB.resize(E + 1);
BB[0] = 1;
for (int e = 1; e <= E; ++e) {
BB[e] = BB[e - 1] * BASE;
}
nodesLen = 1 << (E + 1);
nodes.resize((1 << (E + 1)) + (E + 1) * N);
for (int u = 1; u < 1 << E; ++u) {
nodes[u].l = u << 1;
nodes[u].r = u << 1 | 1;
nodes[u].h = 0;
}
for (int u = 1 << E; u < 1 << (E + 1); ++u) {
nodes[u].l = -1;
nodes[u].r = -1;
nodes[u].h = 0;
}
vector<int> dp(N, -1);
dp[0] = incr(1, A[0]);
vector<int> que(N);
int qb = 0, qe = 0;
for (int i = 1, j = 0; i < N; ++i) {
for (; X[i] - X[j] >= L; ++j) {
if (~dp[j]) {
// push
for (; qe - qb >= 1 && cmp(dp[que[qe - 1]], dp[j]) <= 0; --qe) {}
que[qe++] = j;
}
}
// pop
for (; qe - qb >= 1 && X[i] - X[que[qb]] > R; ++qb) {}
if (qe - qb >= 1) {
dp[i] = incr(dp[que[qb]], A[i]);
}
}
if (~dp[N - 1]) {
vector<int> ans;
dfs(dp[N - 1], ans);
printf("%d\n", (int)ans.size());
for (int h = 0; h < (int)ans.size(); ++h) {
if (h) printf(" ");
printf("%d", ans[h]);
}
puts("");
} else {
puts("-1");
}
}
#ifndef LOCAL
break;
#endif
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3744kb
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:
3 5 4 3 -1
result:
ok 3 lines
Test #2:
score: -100
Wrong Answer
time: 236ms
memory: 3820kb
input:
10000 57 8 11 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 11 16 7 7 10 13 9 14 10 1 12 4 8 13 3 20 16 7 16 19 20 8 19 7 16 6 17 13 7 19 17 11 12 17 6 3 7 8 14 2 4 15 5 18 16 7 20 9 1...
output:
7 20 20 19 14 12 11 3 -1 6 6 5 3 2 1 1 -1 185 20 20 20 20 20 20 20 20 19 19 19 19 19 19 19 19 19 19 19 19 18 18 18 18 18 17 17 17 17 17 17 17 17 16 16 16 16 16 16 16 16 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 14 14 14 14 14 14 14 13 13 13 13 13 13 13 13 13 12 12 12 12 12 12 12 12...
result:
wrong answer 12th lines differ - expected: '139', found: '140'