QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#673087#7949. K-Lotteryucup-team3519WA 12ms75944kbC++176.5kb2024-10-24 20:31:412024-10-24 20:32:06

Judging History

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

  • [2024-10-24 20:32:06]
  • 评测
  • 测评结果:WA
  • 用时:12ms
  • 内存:75944kb
  • [2024-10-24 20:31:41]
  • 提交

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 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, 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);
    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;

    LL seg_time = 0;

    auto add = [&](int x, int cur) -> void {
        seg_time -= clock();
        if(x != 1) range_apply(1, 1, tot, 1, x - 1, 1);
        modify(1, 1, tot, x, mul(cur, powerbase[bit.query(x + 1, N - 1)]));    
        seg_time += clock();
        // cout << "query : " << bit.query(x + 1, N - 1) << endl;
        bit.add(x, 1);
    };
    auto del = [&](int x) -> void {
        seg_time -= clock();
        if(x != 1) range_apply(1, 1, tot, 1, x - 1, -1);
        modify(1, 1, tot, x, 0);
        seg_time += clock();
        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;
    cout << (double)seg_time / CLOCKS_PER_SEC << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 12ms
memory: 75944kb

input:

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

output:

0
0.026778
0

result:

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