| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 824811 |
2023-08-14T10:43:32 Z |
joelgun14 |
Lottery (CEOI18_lot) |
C++17 |
|
337 ms |
596 KB |
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int mod = 1723342759;
int key = 1474064957;
ll mul(ll a, ll b) {
return (a * b) % mod;
}
int main() {
// sub 1 -> brute force
// sub 2 -> ?
// sub 3 -> hashing
// sub 4 -> ?
// sub 5 -> ?
int n, l;
cin >> n >> l;
int a[n + 1];
for(int i = 1; i <= n; ++i)
cin >> a[i];
int q;
cin >> q;
int query[q + 1];
for(int i = 1; i <= q; ++i)
cin >> query[i];
// for subtask 1, just compute for each l, r pair in O(N)
if(n <= 300) {
int diff[n + 1][n + 1];
memset(diff, -1, sizeof(diff));
for(int i = 1; i <= n; ++i) {
for(int r = i + 1; r + l - 1 <= n; ++r) {
diff[i][r] = 0;
for(int k = 0; k < l; ++k) {
if(a[i + k] != a[r + k])
++diff[i][r];
}
//cout << i << " " << r << " " << diff[i][r] << endl;
}
}
for(int i = 1; i <= q; ++i) {
int res[n + 1];
memset(res, 0, sizeof(res));
for(int j = 1; j <= n; ++j) {
for(int k = j + 1; k <= n; ++k) {
//cout << diff[j][k] << endl;
if(diff[j][k] != -1 && diff[j][k] <= query[i])
++res[j], ++res[k];
}
}
for(int j = 1; j <= n - l + 1; ++j)
cout << res[j] << " ";
cout << endl;
}
}
else {
// buat test case query = 0
// pakai hashing utk cek sama atau tidak in O(1)
ll hash[n + 1];
for(int i = 1; i + l - 1 <= n; ++i) {
hash[i] = 0;
for(int j = i; j < i + l; ++j) {
hash[i] = (mul(key, hash[i]) + a[j]) % mod;
}
//cout << hash[i] << " ";
}
//cout << endl;
int res[n + 1];
memset(res, 0, sizeof(res));
for(int i = 1; i + l - 1 <= n; ++i) {
for(int j = 1; j < i; ++j) {
if(hash[i] == hash[j])
++res[i], ++res[j];
}
}
for(int i = 1; i + l - 1 <= n; ++i)
cout << res[i] << " ";
cout << endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
296 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
3 ms |
596 KB |
Output is correct |
| 9 |
Correct |
3 ms |
596 KB |
Output is correct |
| 10 |
Correct |
3 ms |
596 KB |
Output is correct |
| 11 |
Correct |
3 ms |
596 KB |
Output is correct |
| 12 |
Correct |
4 ms |
596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
296 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
3 ms |
596 KB |
Output is correct |
| 9 |
Correct |
3 ms |
596 KB |
Output is correct |
| 10 |
Correct |
3 ms |
596 KB |
Output is correct |
| 11 |
Correct |
3 ms |
596 KB |
Output is correct |
| 12 |
Correct |
4 ms |
596 KB |
Output is correct |
| 13 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
78 ms |
460 KB |
Output is correct |
| 2 |
Correct |
42 ms |
468 KB |
Output is correct |
| 3 |
Correct |
33 ms |
460 KB |
Output is correct |
| 4 |
Correct |
59 ms |
508 KB |
Output is correct |
| 5 |
Correct |
336 ms |
536 KB |
Output is correct |
| 6 |
Correct |
115 ms |
468 KB |
Output is correct |
| 7 |
Correct |
337 ms |
484 KB |
Output is correct |
| 8 |
Correct |
290 ms |
496 KB |
Output is correct |
| 9 |
Correct |
76 ms |
492 KB |
Output is correct |
| 10 |
Correct |
69 ms |
536 KB |
Output is correct |
| 11 |
Correct |
30 ms |
332 KB |
Output is correct |
| 12 |
Correct |
203 ms |
464 KB |
Output is correct |
| 13 |
Correct |
328 ms |
488 KB |
Output is correct |
| 14 |
Correct |
327 ms |
488 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
78 ms |
460 KB |
Output is correct |
| 2 |
Correct |
42 ms |
468 KB |
Output is correct |
| 3 |
Correct |
33 ms |
460 KB |
Output is correct |
| 4 |
Correct |
59 ms |
508 KB |
Output is correct |
| 5 |
Correct |
336 ms |
536 KB |
Output is correct |
| 6 |
Correct |
115 ms |
468 KB |
Output is correct |
| 7 |
Correct |
337 ms |
484 KB |
Output is correct |
| 8 |
Correct |
290 ms |
496 KB |
Output is correct |
| 9 |
Correct |
76 ms |
492 KB |
Output is correct |
| 10 |
Correct |
69 ms |
536 KB |
Output is correct |
| 11 |
Correct |
30 ms |
332 KB |
Output is correct |
| 12 |
Correct |
203 ms |
464 KB |
Output is correct |
| 13 |
Correct |
328 ms |
488 KB |
Output is correct |
| 14 |
Correct |
327 ms |
488 KB |
Output is correct |
| 15 |
Incorrect |
100 ms |
448 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
296 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
3 ms |
596 KB |
Output is correct |
| 9 |
Correct |
3 ms |
596 KB |
Output is correct |
| 10 |
Correct |
3 ms |
596 KB |
Output is correct |
| 11 |
Correct |
3 ms |
596 KB |
Output is correct |
| 12 |
Correct |
4 ms |
596 KB |
Output is correct |
| 13 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
