QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#783264#7949. K-LotteryNYCU_MyGOCompile Error//C++205.7kb2024-11-26 04:33:402024-11-26 04:33:40

Judging History

你现在查看的是最新测评结果

  • [2024-11-26 04:33:40]
  • 评测
  • [2024-11-26 04:33:40]
  • 提交

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;
    }
    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];
        auto& u = rev_ticket[i];
        u.resize(K);
        for (int j = 0; j < K; j++)
            u[v[j]-1] = j+1;
        i128 hash = 0;
        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);

    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]-1])
                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+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,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")

#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/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:175,
                 from answer.code:3:
/usr/include/c++/13/bits/allocator.h: In destructor ‘constexpr std::_Rb_tree<__int128, std::pair<const __int128, std::vector<int> >, std::_Select1st<std::pair<const __int128, std::vector<int> > >, std::less<__int128>, std::allocator<std::pair<const __int128, std::vector<int> > > >::_Rb_tree_impl<std::less<__int128>, true>::~_Rb_tree_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = std::_Rb_tree_node<std::pair<const __int128, std::vector<int> > >]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/map:62,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:152:
/usr/include/c++/13/bits/stl_tree.h:662:16: note: called from here
  662 |         struct _Rb_tree_impl
      |                ^~~~~~~~~~~~~