QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#725117 | #7949. K-Lottery | gugugaga# | TL | 0ms | 3660kb | C++14 | 2.7kb | 2024-11-08 16:20:08 | 2024-11-08 16:20:09 |
Judging History
answer
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
namespace std {
template <int D, typename T>
struct Vec : public vector<Vec<D - 1, T>> {
static_assert(D >= 1);
template <typename... Args>
Vec(int n = 0, Args... args) : vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...)) {}
};
template <typename T>
struct Vec<1, T> : public vector<T> {
Vec(int n = 0, T val = T()) : std::vector<T>(n, val) {}
};
template <class Fun>
class y_combinator_result {
Fun fun_;
public:
template <class T>
explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}
template <class... Args>
decltype(auto) operator()(Args &&...args) {
return fun_(std::ref(*this), std::forward<Args>(args)...);
}
};
template <class Fun>
decltype(auto) y_combinator(Fun &&fun) {
return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
} // namespace std
const long long base = 1e5 + 1;
const long long mod[3] = {(long long) 1e9 + 7, (long long) 1e9 + 9, (long long) 1e9 + 10};
void solve() {
int k, m, n; cin >> k >> m >> n;
Vec<2, int> a(m, k);
map<long long, int> mp;
for (int i = 0; i < m; i++) {
vector<long long> hs(2);
for (int j = 0; j < k; j++) {
cin >> a[i][j];
for (int l = 0; l < 2; l++) {
hs[l] = (hs[l] * base + a[i][j]) % mod[l];
}
}
long long code = hs[0] * mod[3] + hs[1];
assert(mp[code] == 0);
mp[code] = i + 1;
}
vector<int> b(n);
for (int i = 0; i < n; i++) {
cin >> b[i];
if (i >= k - 1) {
vector<int> rrh, arr;
for (int j = i - k + 1; j <= i; j++) {
arr.push_back(b[j]);
rrh.push_back(b[j]);
}
sort(rrh.begin(), rrh.end());
rrh.resize(unique(rrh.begin(), rrh.end()) - rrh.begin());
vector<long long> hs(2);
for (auto &j : arr) {
j = upper_bound(rrh.begin(), rrh.end(), j) - rrh.begin();
for (int l = 0; l < 2; l++) {
hs[l] = (hs[l] * base + j) % mod[l];
}
}
long long code = hs[0] * mod[3] + hs[1];
if (mp[code]) {
int idx = mp[code] - 1;
for (int j = 0; j < k; j++) cout << a[idx][j] << " ";
exit(0);
}
}
}
cout << 0;
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// ?cin >> t;
while (t--) {
solve();
cout << endl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3660kb
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: 0ms
memory: 3620kb
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: 0ms
memory: 3628kb
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: -100
Time Limit Exceeded
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...