QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#781231 | #7949. K-Lottery | NYCU_MyGO# | WA | 760ms | 12536kb | C++20 | 5.3kb | 2024-11-25 15:20:49 | 2024-11-25 15:20:50 |
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; i64 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 i64 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<i64> Ha(M);
// vector<vector<int>> rev_ticket(M);
map<i64, vector<int>> mp{};
for (int i = 0; i < M; i++) {
auto& v = tickets[i];
i64 hash = 0;
for (auto x: v)
hash = (hash * P + x) % MOD;
Ha[i] = hash;
mp[hash].emplace_back(i);
}
debug(Ha);
TreapP root = nullptr;
for (int i = 0; i < K; i++)
insert(root, seq[i], i);
i64 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;
i64 hh = (H(root) - idi * p % MOD + MOD) % 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;
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())
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
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4032kb
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: 3820kb
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: 1ms
memory: 3984kb
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: 760ms
memory: 12536kb
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'