QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#673110#7949. K-Lotteryucup-team3519TL 1038ms97752kbC++176.5kb2024-10-24 20:36:212024-10-24 20:36:22

Judging History

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

  • [2024-10-24 20:36:22]
  • 评测
  • 测评结果:TL
  • 用时:1038ms
  • 内存:97752kb
  • [2024-10-24 20:36:21]
  • 提交

answer

#pragma GCC optimize(3, "Ofast")
#include<bits/stdc++.h>
using namespace std;
typedef __int128_t LLL;
#define V vector
#define pb push_back
typedef unsigned long long ULL;
typedef long long LL;
#define lb lower_bound
#define all0(x) (x).begin(), (x).end()
#define all1(x) (x).begin() + 1, (x).end()
const int N = 1e6 + 10;
const LL mod = 444445555566666677;
const LL base = 23333;


LL powerbase[N];
LL ipowerbase[N];

LL get_powerbase(LL x) {
    if(x < 0) return ipowerbase[-x];
    return powerbase[x];
}

LL MOD(LL x) {
    if(x >= mod) x -= mod;
    if(x < 0) x += mod;
    return x;
}
LL mul(LL a, LL b) {
    if(a == 0 || b == 0) return 0;
    return (__int128_t)a * b % mod;
}
LL qpow(LL x, LL k) {
    LL ans = 1;
    while(k) {
        if(k & 1) ans = mul(ans, x);
        k /= 2;
        x = mul(x, x);
    }
    return ans;
}
struct Node {
    LL sum_val;
    LL mul_pbs;
    Node() {
        sum_val = 0, mul_pbs = 0;
    }
} seg[N << 2];
void pull_up(int node) {
    seg[node].sum_val = MOD(seg[node << 1].sum_val + seg[node << 1 | 1].sum_val);
}
void apply(int node, LL mul_pbs) {
    seg[node].sum_val = mul(seg[node].sum_val, get_powerbase(mul_pbs));
    seg[node].mul_pbs += mul_pbs;
}
void push_down(int node) {
    if (seg[node].mul_pbs) {
        LL &tag = seg[node].mul_pbs;
        apply(node << 1, tag);
        apply(node << 1 | 1, tag);
        tag = 0;
    }
}
void modify(int node, int L, int R, int pos, LL val) {
    if (L == R) {
        seg[node].sum_val = val;
        return;
    }
    push_down(node);
    int mid = (L + R) / 2;
    if (pos <= mid) modify(node << 1, L, mid, pos, val);
    else modify(node << 1 | 1, mid + 1, R, pos, val);
    pull_up(node);
}
void seg_show(int node, int L, int R, int pos) {
    if (L == R) {
        cout << "sum _val : " << seg[node].sum_val << endl;
        cout << "tag  : " << seg[node].mul_pbs << endl;
        // cout << "fine : " << seg[node].fine << endl;
        return;
    }
    push_down(node);
    int mid = (L + R) / 2;
    if (pos <= mid) seg_show(node << 1, L, mid, pos);
    else seg_show(node << 1 | 1, mid + 1, R, pos);
    pull_up(node);
}
void range_apply(int node, int L, int R, int l, int r, LL tag) {
    if (l <= L && R <= r) {
        apply(node, tag);
        return;
    }
    push_down(node);
    int mid = (L + R) / 2;
    if (l <= mid) range_apply(node << 1, L, mid, l, r, tag);
    if (r > mid) range_apply(node << 1 | 1, mid + 1, R, l, r, tag);
    pull_up(node);
}

namespace fast {
    char B[1 << 18], *S = B, *T = B;
    #define getc() (S == T && (T = (S = B) + fread(B, 1, 1 << 18, stdin), S == T) ? 0 : *S++)
    int read() {
        int ret = 0; 
        char c;
        while(c = getc(), c < '0' || c > '9');
        for(; c >= '0' && c <= '9'; c = getc()) ret = ret * 10 + c - '0';
        return ret;
    }
}
using fast::read;

mt19937 mrand(chrono::steady_clock().now().time_since_epoch().count());

struct BIT {
    LL fenT[N];
    void add(int x, LL d) {
        assert(x > 0);
        while(x < N) {
            fenT[x] = fenT[x] + d;
            x += x & (-x);
        }
    }
    LL query(int x) {
        LL ans = 0;
        while(x >= 1) {
            ans = ans + fenT[x];
            x -= x & (-x);
        }
        return ans;
    }
    LL query(int l, int r) {
        return query(r) - query(l - 1);
    }
}bit;
int main() {
    // ios::sync_with_stdio(0), cin.tie(0);
    // int k = 1000, m = 1000;
    // int n = 1e6;
    int k, m, n; cin >> k >> m >> n;
    // int k = 1000, m = 1000;
    // int n = 1e6;
    V<LL> hs(m + 1);
    V<V<int>> tab(m + 1);
    for(int i = 1; i <= m; i++) {
        V<int> a(k + 1);
        // iota(all1(a), 1);
        // shuffle(all1(a), mrand);
        for(int j = 1; j <= k; j++) a[j] = read();
        tab[i] = a;
        V<int> pos(k + 1);
        for(int j = 1; j <= k; j++) pos[a[j]] = j;
        LL cur = 0;
        for(int j = 1; j <= k; j++) {
            cur = MOD(mul(cur, base) + pos[j]);
        }
        hs[i] = cur;
    }
    map<LL, int> mp;
    for(int i = 1; i <= m; i++) mp[hs[i]] = i;
    // cout << (double)clock() / CLOCKS_PER_SEC << endl;

    V<int> sheet(n + 1);
    for(int i = 1; i <= n; i++) sheet[i] = read();
    V<int> ord(n + 1);
    iota(all1(ord), 1);
    sort(all1(ord), [&](int x, int y) {
        return sheet[x] < sheet[y];
    });
    for(int i = 1; i <= n; i++) sheet[ord[i]] = i;

    int tot = 1e6;
    powerbase[0] = 1;
    for(int i = 1; i <= tot; i++) powerbase[i] = mul(powerbase[i - 1], base);
    ipowerbase[tot] = qpow(powerbase[tot], mod - 2);
    for(int i = tot - 1; i >= 0; i--) {
        ipowerbase[i] = mul(ipowerbase[i + 1], base);
    }
    auto show = [&](int n) -> void {
        for(int i = 1; i <= n; i++) seg_show(1, 1, tot, i);
    };
    // show(10);

    LL basic = 0;
    for(int i = 1; i <= k; i++) {
        basic = MOD(mul(basic, base) + 1);
    }

    // cout << (double)clock() / CLOCKS_PER_SEC << endl;

    // for(int i = 1; i <= 3; i++) cout << powerbase[i] << " ";
    // cout << endl;


    auto add = [&](int x, int cur) -> void {
        if(x != 1) range_apply(1, 1, tot, 1, x - 1, 1);
        modify(1, 1, tot, x, mul(cur, get_powerbase(bit.query(x + 1, N - 1))));    
        // cout << "query : " << bit.query(x + 1, N - 1) << endl;
        bit.add(x, 1);
    };
    auto del = [&](int x) -> void {
        if(x != 1) range_apply(1, 1, tot, 1, x - 1, -1);
        modify(1, 1, tot, x, 0);
        bit.add(x, -1);
    };
    auto get = [&](int cur) -> LL {
        return MOD(seg[1].sum_val - mul(basic, cur - k));
    };

    // for(int i = 1; i <= n; i++) cout << sheet[i] << " ";
    // cout << endl;

    V<LL> hav;
    for(int i = 1; i <= m; i++) hav.pb(hs[i]);
    sort(all0(hav));

    auto got = [&](LL x) {
        auto it = lb(all0(hav), x);
        if(*it == x) return 1;
        return 0;
    };

    for(int i = 1; i <= n; i++) {
        // cout << "I : " << i << endl;
        if(i - k >= 1) del(sheet[i - k]);
        add(sheet[i], i);
        //i -> k
        // cout << "i : " << i << endl;
        // show(10);
        if(i >= k && got(get(i))) {
            int id = mp[get(i)];
            for(int i = 1; i <= k; i++) cout << tab[id][i] << " ";
            cout << endl;
            // cout << (double)clock() / CLOCKS_PER_SEC << endl;
            return 0;
        }
        // cout << get() << endl;
    }
    cout << 0 << endl;

    // cout << (double)clock() / CLOCKS_PER_SEC << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 29ms
memory: 85280kb

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: 19ms
memory: 84652kb

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: 30ms
memory: 85244kb

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: 0
Accepted
time: 1038ms
memory: 97752kb

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:

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 5037 38 5038 39 50...

result:

ok single line: '1 5001 2 5002 3 5003 4 5004 5 ...4998 9998 4999 9999 5000 10000 '

Test #5:

score: -100
Time Limit Exceeded

input:

10000 10 1000000
7171 4541 8189 3253 6694 2078 7384 1786 7847 5040 953 4126 4806 3532 7875 8531 3543 2706 8565 1509 2092 4125 6110 5251 6314 4574 6726 8900 9328 8639 3990 5234 9012 5023 3289 2825 8038 3593 2249 337 6252 3831 7967 3839 2815 540 3754 1009 8772 2939 2845 5067 6587 2615 375 7252 9940 18...

output:


result: