QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#712020#7949. K-Lotterykizen#WA 0ms3828kbC++204.4kb2024-11-05 14:19:022024-11-05 14:19:02

Judging History

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

  • [2024-11-05 14:19:02]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3828kb
  • [2024-11-05 14:19:02]
  • 提交

answer

#include <bits/stdc++.h>

#ifndef LOCAL
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#endif

#define sz(v) ((int)v.size())
#define all(v) v.begin(), v.end()
#define pb push_back
#define pi array<int, 2>
#define comp(v) (sort(all(v)), v.erase(unique(all(v)), v.end()))
#define lb(v, x) (lower_bound(all(v), x) - v.begin())

using namespace std;

#define int long long

const pi v1 = {5, 724585409557367ll};
// const pi v1 = {97, 805306457};

struct Seg{
    int n;
    vector<int> tr;
    Seg(int m){
        n = m + 4;
        tr.resize(n * 4 + 4);
    }

    void push(int x, int s, int e, int pos, int val){
        if(s == e){
            tr[x] = val;
            return;
        }
        int m = s + e >> 1;
        if(pos <= m) push(x * 2, s, m, pos, val);
        else push(x * 2 + 1, m + 1, e, pos, val);
        tr[x] = (tr[x * 2] + tr[x * 2 + 1]) % v1[1];
    }

    int get(int x, int s, int e, int fs, int fe){
        if(fe < s || fs > e || fs > fe) return 0;
        if(fs <= s && fe >= e) return tr[x];
        int m = s + e >> 1;
        return (get(x * 2, s, m, fs, fe) + get(x * 2 + 1, m + 1, e, fs, fe)) % v1[1];
    }
};


int pw(int x, int y, int md){
    if(!y) return 1;
    if(y == 1) return x % md;
    int v = pw(x, y >> 1, md);
    v = ((__int128)v * v) % md;
    if(y & 1) v = ((__int128)v * x) % md;
    return v;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    long long k, m, n; cin >> k >> m >> n;
    vector<vector<long long>> a(m, vector<long long>(k));
    for(int i = 0; i < m; ++i){
        for(int j = 0; j < k; ++j){
            cin >> a[i][j]; --a[i][j];
        }
    }
    
    vector<__int128> hsh(m + 1);
    for(int i = 0; i < m; ++i){
        Seg tr(k + 4);
        for(int j = 0; j < k; ++j){
            __int128 rv = tr.get(1, 0, k - 1, a[i][j], k - 1);
            (rv *= pw(v1[0], j, v1[1])) %= v1[1];
            (hsh[i] += rv) %= v1[1];

            tr.push(1, 0, k - 1, a[i][j], pw(v1[0], j * k, v1[1]));
        }
    }

    vector<long long> p(n);
    for(int i = 0; i < n; ++i){
        cin >> p[i];
    }
    auto srt = p;
    comp(srt);
    for(int i = 0; i < n; ++i){
        p[i] = lb(srt, p[i]);
    }

    Seg tr(n + 4), rt(n + 4);
    for(int j = 0; j < k; ++j){
        __int128 rv = tr.get(1, 0, n - 1, p[j], n - 1);
        (rv *= pw(v1[0], j, v1[1])) %= v1[1];
        (hsh[m] += rv) %= v1[1];

        tr.push(1, 0, n - 1, p[j], pw(v1[0], j * k, v1[1]));
        rt.push(1, 0, n - 1, p[j], pw(v1[0], j, v1[1]));
    }

    vector<int> id(m);
    iota(all(id), 0);
    sort(all(id), [&](int x, int y){return hsh[x] < hsh[y];});

    __int128 inv1 = pw(v1[0], v1[1] - 2, v1[1]);
    __int128 inv1k1 = pw(inv1, k + 1, v1[1]);
   __int128 inv1k = pw(inv1, k, v1[1]);
    __int128 k1 = pw(v1[0], k - 1, v1[1]);

    __int128 inv1kinv = pw(inv1k, v1[1] - 2, v1[1]);

    // for(int i = 0; i <= m; ++i){
    //     cout << hsh[i] << endl;
    // }

    int trgop = 1, rtgop = 1;
    int trgopinv = 1, rtgopinv = 1;
    for(int i = 0; i + k <= n; ++i){
        int pos = lower_bound(id.begin(), id.end(), m, [&](int x, int y){return hsh[x] < hsh[y];}) - id.begin();
        if(pos < sz(id) && hsh[id[pos]] == hsh[m]){
            for(int j = 0; j < k; ++j){
                cout << a[id[pos]][j] + 1 << ' ';
            }
            return 0;
        }

        if(i + k < n){
            rt.push(1, 0, n - 1, p[i], 0);
            tr.push(1, 0, n - 1, p[i], 0);

            // cout << hsh[m] << ' ';

            (hsh[m] += v1[1] - (__int128)rt.get(1, 0, n - 1, 0, p[i] - 1) * rtgop % v1[1]) %= v1[1];

            // cout << hsh[m] << ' ';

            (hsh[m] *= inv1k1) %= v1[1];
            (trgop *= inv1k) %= v1[1];
            (rtgop *= inv1) %= v1[1];
            (trgopinv *= inv1kinv) %= v1[1];
            (rtgopinv *= v1[0]) %= v1[1];

            // cout << hsh[m] << ' ';

            __int128 rv = (__int128)tr.get(1, 0, n - 1, p[i + k], n - 1) * trgop % v1[1];
            (rv *= k1) %= v1[1];
            (hsh[m] += rv) %= v1[1];

            tr.push(1, 0, n - 1, p[i + k], (__int128)pw(k1, k, v1[1]) * trgopinv % v1[1]);
            rt.push(1, 0, n - 1, p[i + k], (__int128)k1 * rtgopinv % v1[1]);

            // cout << endl;
        }
    }

    cout << 0;

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3828kb

input:

3 2 10
1 2 3
1 3 2
20 35 10 7 99 53 72 33 88 16

output:

0

result:

wrong answer 1st lines differ - expected: '1 3 2', found: '0'