QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#783272 | #7949. K-Lottery | NYCU_MyGO | Compile Error | / | / | C++20 | 6.2kb | 2024-11-26 06:25:05 | 2024-11-26 06:25:05 |
Judging History
answer
#ifndef MyGO
#define MyGO
#include MyGO __FILE__ MyGO
/*
mt19937 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); }
*/
using ull = unsigned long long;
inline ull splitmix64() {
static ull x = 0x1337deadbeefcace;
// change to `static ull x = SEED;` for DRBG
ull z = (x += 0x9E3779B97F4A7C15);
z = (z ^ (z >> 30)) * 0xBF58476D1CE4E5B9;
z = (z ^ (z >> 27)) * 0x94D049BB133111EB;
return z ^ (z >> 31);
}
int randint(int x) { return splitmix64() % x; }
constexpr int MAXN = 1e6+5;
constexpr int MAXK = 1e4+5;
constexpr i64 P = 1e6+3;
constexpr i64 MOD = 1e12+39;
i64 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;
}
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{};
#pragma GCC ivdep
for (int i = 0; i < M; i++) {
auto& v = tickets[i];
auto& u = rev_ticket[i];
u.resize(K);
#pragma GCC ivdep
for (int j = 0; j < K; j++)
u[v[j]-1] = j+1;
i64 hash = 0;
#pragma GCC ivdep
for (auto x: u)
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+1);
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]);
#pragma GCC ivdep
for (int i = 0; i < K; i++)
if (seq[y+i] != v[tickets[x][i]-1])
return false;
return true;
};
int ans = -1;
#pragma GCC ivdep
for (int i = K; i <= N; i++) {
int p = i - K; // [p, i)
i64 hh = (H(root) - (i128)idi * p % MOD + MOD) % MOD;
assert(hh >= 0 and hh < MOD);
debug(i, hh);
auto it = mp.find(hh);
if (it != mp.end()) {
#pragma GCC ivdep
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+1);
}
debug(ans);
// if (ans != -1) debug(tickets[ans]);
if (ans == -1)
cout << 0 << '\n';
else
for (auto x: tickets[ans])
cout << x << ' ';
}
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
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC optimize("no-math-errno,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
#pragma GCC target("popcnt,abm,mmx,avx,arch=skylake")
#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
In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/gthr.h:148, from /usr/include/c++/13/ext/atomicity.h:35, from /usr/include/c++/13/bits/ios_base.h:39, from /usr/include/c++/13/streambuf:43, from /usr/include/c++/13/bits/streambuf_iterator.h:35, from /usr/include/c++/13/iterator:66, from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:54, from answer.code:195, from answer.code:3: /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:102:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute 102 | __gthrw(pthread_once) | ^~~~~~~ /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:102:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:103:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute 103 | __gthrw(pthread_getspecific) | ^~~~~~~ /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:103:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:104:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute 104 | __gthrw(pthread_setspecific) | ^~~~~~~ /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:104:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:106:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute 106 | __gthrw(pthread_create) | ^~~~~~~ /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:106:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:107:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute 107 | __gthrw(pthread_join) | ^~~~~~~ /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:107:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:108:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute 108 | __gthrw(pthread_equal) | ^~~~~~~ /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:108:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:109:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute 109 | __gthrw(pthread_self) | ^~~~~~~ /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:109:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:110:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute 110 | __gthrw(pthread_detach) | ^~~~~~~ /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:110:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:112:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute 112 | __gthrw(pthread_cancel) | ^~~~~~~ /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:112:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:114:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute 114 | __gthrw(sched_yield) | ^~~~~~~ /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:114:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:116:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute 116 | __gthrw(pthread_mutex_lock) | ^~~~~~~ /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:116:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:117:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute 117 | __gthrw(pthread_mutex_trylock) | ^~~~~~~ /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:117:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:119:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute 119 | __gthrw(pthread_mutex_timedlock) | ^~~~~~~ /usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:119:1: error: attribute value ‘arch=skylake’ was already specified in ‘target’ attribute /usr/include/x86_64-linu...