QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#673087 | #7949. K-Lottery | ucup-team3519 | WA | 12ms | 75944kb | C++17 | 6.5kb | 2024-10-24 20:31:41 | 2024-10-24 20:32:06 |
Judging History
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'