QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#712020 | #7949. K-Lottery | kizen# | WA | 0ms | 3828kb | C++20 | 4.4kb | 2024-11-05 14:19:02 | 2024-11-05 14:19:02 |
Judging History
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'