QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#781287 | #7949. K-Lottery | NYCU_MyGO# | WA | 761ms | 12688kb | C++20 | 5.5kb | 2024-11-25 15:32:19 | 2024-11-25 15:32:24 |
Judging History
answer
#ifndef MyGO
#define MyGO
#include MyGO __FILE__ MyGO
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T>
T randint(T x) { return uniform_int_distribution<T>(0, x-1)(rng); }
constexpr int MAXN = 1e6+5;
constexpr int MAXK = 1e4+5;
constexpr i128 P = 1e6+3;
constexpr i128 MOD = 1e12+39;
i128 PPOW[MAXK];
struct Treap;
using TreapP = Treap*;
struct Treap {
int sz, data;
int id; i128 hash;
TreapP l, r;
Treap(int k, int i) : sz(1), data(k), id(i), hash(i), l(0), r(0) {}
};
inline int sz(TreapP o) { return o ? o->sz : 0; }
inline i128 H(TreapP o) { return o ? o->hash : 0; }
void pull(TreapP o) {
auto lsz = sz(o->l), rsz = sz(o->r);
o->sz = lsz + 1 + rsz;
o->hash = ((i128)H(o->l) * PPOW[rsz+1] + o->id * PPOW[rsz] + H(o->r)) % MOD;
}
void push(TreapP o) {}
TreapP merge(TreapP a, TreapP b) {
if (!a or !b) return a ? a : b;
TreapP r;
if (randint(sz(a) + sz(b)) < sz(a))
r = a, push(r), r->r = merge(a->r, b);
else r = b, push(r), r->l = merge(a, b->l);
return pull(r), r;
}
void split(TreapP o, TreapP &a, TreapP &b, int k) {
if (!o) return a = b = 0, void();
push(o);
if (o->data <= k)
a = o, split(o->r, a->r, b, k), pull(a);
else b = o, split(o->l, a, b->l, k), pull(b);
}
void split2(TreapP o, TreapP &a, TreapP &b, int k) {
if (sz(o) <= k) return a = o, b = 0, void();
push(o);
if (sz(o->l) + 1 <= k)
a = o, split2(o->r, a->r, b, k - sz(o->l) - 1);
else b = o, split2(o->l, a, b->l, k);
pull(o);
}
bool erase(TreapP &o, int k) {
if (!o) return 0;
if (o->data == k) {
TreapP t = o;
push(o), o = merge(o->l, o->r);
delete t;
return 1;
}
TreapP &t = k < o->data ? o->l : o->r;
return erase(t, k) ? pull(o), 1 : 0;
}
void insert(TreapP &o, int k, int v) {
TreapP a, b;
split(o, a, b, k);
o = merge(a, merge(new Treap(k, v), b));
}
void solve() {
int K, M, N;
cin >> K >> M >> N;
vector<vector<int>> tickets(M);
for (auto &v: tickets) {
v.resize(K);
for (auto &x: v) cin >> x, x--;
}
vector<int> seq(N);
for (auto &x: seq) cin >> x;
vector<i128> Ha(M);
// vector<vector<int>> rev_ticket(M);
map<i128, vector<int>> mp{};
for (int i = 0; i < M; i++) {
auto& v = tickets[i];
i128 hash = 0;
for (auto x: v)
hash = (hash * P + x) % MOD;
Ha[i] = hash;
mp[hash].emplace_back(i);
assert(hash >= 0 and hash < MOD);
}
debug(Ha);
TreapP root = nullptr;
for (int i = 0; i < K; i++)
insert(root, seq[i], i);
i128 idi = 0;
for (int i = 0; i < K; i++)
idi = (idi * P + 1) % MOD;
debug(idi);
auto check = [=](int x, int y) {
debug(x, y);
vector<int> v(seq.begin()+y, seq.begin()+y+K);
sort(ALL(v));
debug(v);
debug(tickets[x]);
for (int i = 0; i < K; i++)
if (seq[y+i] != v[tickets[x][i]])
return false;
return true;
};
int ans = -1;
for (int i = K; i <= N; i++) {
int p = i - K; // [p, i)
i128 hh = (H(root) - idi * p % MOD + MOD) % MOD;
assert(hh >= 0 and hh < MOD);
debug(i, hh);
auto it = mp.find(hh);
if (it != mp.end()) {
for (auto x: it->second) {
if (check(x, p)) {
ans = x;
break;
}
}
if (ans != -1) break;
}
if (i == N) break;
assert(erase(root, seq[p]));
insert(root, seq[i], i);
}
debug(ans);
// if (ans != -1) debug(tickets[ans]);
if (ans == -1)
cout << 0 << '\n';
else
for (auto x: tickets[ans])
cout << x+1 << ' ';
}
int32_t main() {
fastIO();
PPOW[0] = 1;
for (int i = 1; i < MAXK; i++)
PPOW[i] = PPOW[i-1] * P % MOD;
int t = 1;
// cin >> t;
while (t--) solve();
}
#else
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
// #define int i64
using pii = pair<int, int>;
#define ee emplace
#define eb emplace_back
#define ef emplace_front
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())
ostream& operator<< (ostream& os, const i128 v) {
return os << (i64)v;
}
template <typename T>
ostream& operator << (ostream &os, const vector<T> &vec) {
for (int i = 0; i < SZ(vec); ++i) {
if (i) os << " ";
os << vec[i];
}
return os;
}
#ifdef local
#define fastIO() void()
#define debug(...) \
fprintf(stderr, "\u001b[33m"), \
fprintf(stderr, "Line %d: (%s) = ", __LINE__, #__VA_ARGS__), \
_do(__VA_ARGS__), \
fprintf(stderr, "\u001b[0m")
template <typename T> void _do(T &&_t) { cerr << _t << "\n"; }
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) { cerr << _t << ", ", _do(_u...); }
#else
#define fastIO() cin.tie(0)->sync_with_stdio(0)
#define debug(...) void()
#endif
template <typename T, typename U> bool chmin(T &lhs, U rhs) { return lhs > rhs ? lhs = rhs, 1 : 0; }
template <typename T, typename U> bool chmax(T &lhs, U rhs) { return lhs < rhs ? lhs = rhs, 1 : 0; }
#endif
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4000kb
input:
3 2 10 1 2 3 1 3 2 20 35 10 7 99 53 72 33 88 16
output:
1 3 2
result:
ok single line: '1 3 2 '
Test #2:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
4 5 10 1 2 3 4 1 2 4 3 3 4 1 2 4 1 2 3 4 2 3 1 19 31 9 1 89 48 63 30 78 12
output:
4 2 3 1
result:
ok single line: '4 2 3 1 '
Test #3:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
3 3 7 1 3 2 2 3 1 2 1 3 11 22 33 44 55 66 77
output:
0
result:
ok single line: '0'
Test #4:
score: -100
Wrong Answer
time: 761ms
memory: 12688kb
input:
10000 10 1000000 1 5001 2 5002 3 5003 4 5004 5 5005 6 5006 7 5007 8 5008 9 5009 10 5010 11 5011 12 5012 13 5013 14 5014 15 5015 16 5016 17 5017 18 5018 19 5019 20 5020 21 5021 22 5022 23 5023 24 5024 25 5025 26 5026 27 5027 28 5028 29 5029 30 5030 31 5031 32 5032 33 5033 34 5034 35 5035 36 5036 37 5...
output:
0
result:
wrong answer 1st lines differ - expected: '1 5001 2 5002 3 5003 4 5004 5 ... 4998 9998 4999 9999 5000 10000', found: '0'