#include <stdio.h>
#include <stdlib.h>
#define N 150000
#define K 400
#define M 200000
#define MD 0x7fffffff
int max(int a, int b) { return a > b ? a : b; }
int *ek[M], *ev[M], eo[M], X = 123454321;
void init() {
int h;
for (h = 0; h < M; h++) {
ek[h] = (int *) malloc(2 * sizeof *ek[h]);
ev[h] = (int *) malloc(2 * sizeof *ev[h]);
}
}
int hash(int k) {
return ((long long) k * X % MD) % M;
}
void add(int k) {
int h = hash(k), o;
for (o = eo[h]; o--; )
if (ek[h][o] == k)
return;
o = eo[h]++;
if (o >= 2 && (o & o - 1) == 0) {
ek[h] = (int *) realloc(ek[h], o * 2 * sizeof *ek[h]);
ev[h] = (int *) realloc(ev[h], o * 2 * sizeof *ev[h]);
}
ek[h][o] = k, ev[h][o] = 0;
}
int incr(int k) {
int h = hash(k), o;
for (o = eo[h]; o--; )
if (ek[h][o] == k)
return ++ev[h][o];
return 0;
}
int main() {
static int aa[N + K];
static char used[N + K];
int n, k, i, j, s, cnt;
init();
scanf("%d%d", &n, &k);
for (i = 0; i < n + k; i++)
scanf("%d", &aa[i]);
for (i = 0; i <= k; i++)
for (j = n + k - 1; j > i && j >= n - 1; j--)
add(aa[i] + aa[j]);
for (i = 0; i < n + k; i++)
for (j = max(n - 1 - i, i + 1); j < n + k && i + j <= n - 1 + k * 2; j++)
if (incr(s = aa[i] + aa[j]) == n / 2) {
for (i = 0, j = n + k - 1, cnt = 0; i < j && cnt < n / 2; i++) {
while (i < j && aa[i] + aa[j] > s)
j--;
if (i < j && aa[i] + aa[j] == s)
used[i] = used[j] = 1, cnt--;
}
for (i = 0; i < n + k; i++)
if (used[i])
printf("%d ", aa[i]);
printf("\n");
return 0;
}
return 0;
}
Compilation message
tabletennis.c: In function 'add':
tabletennis.c:33:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
33 | if (o >= 2 && (o & o - 1) == 0) {
| ~~^~~
tabletennis.c: In function 'main':
tabletennis.c:55:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
55 | scanf("%d%d", &n, &k);
| ^~~~~~~~~~~~~~~~~~~~~
tabletennis.c:57:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
57 | scanf("%d", &aa[i]);
| ^~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
15956 KB |
Output is correct |
2 |
Correct |
14 ms |
15968 KB |
Output is correct |
3 |
Correct |
13 ms |
15964 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
16340 KB |
Output is correct |
2 |
Correct |
35 ms |
19604 KB |
Output is correct |
3 |
Correct |
36 ms |
19532 KB |
Output is correct |
4 |
Correct |
34 ms |
19592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
39 ms |
19524 KB |
Output is correct |
2 |
Correct |
38 ms |
19628 KB |
Output is correct |
3 |
Correct |
36 ms |
19660 KB |
Output is correct |
4 |
Correct |
36 ms |
19592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
16644 KB |
Output is correct |
2 |
Correct |
12 ms |
16700 KB |
Output is correct |
3 |
Correct |
12 ms |
16644 KB |
Output is correct |
4 |
Correct |
12 ms |
16724 KB |
Output is correct |
5 |
Correct |
13 ms |
16664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
16012 KB |
Output is correct |
2 |
Correct |
10 ms |
16080 KB |
Output is correct |
3 |
Correct |
11 ms |
16264 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
16468 KB |
Output is correct |
2 |
Correct |
16 ms |
16600 KB |
Output is correct |
3 |
Correct |
14 ms |
16672 KB |
Output is correct |
4 |
Correct |
14 ms |
16600 KB |
Output is correct |
5 |
Correct |
11 ms |
16508 KB |
Output is correct |
6 |
Correct |
12 ms |
16364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
16468 KB |
Output is correct |
2 |
Correct |
62 ms |
20212 KB |
Output is correct |
3 |
Correct |
52 ms |
20180 KB |
Output is correct |
4 |
Correct |
60 ms |
20168 KB |
Output is correct |
5 |
Correct |
61 ms |
20004 KB |
Output is correct |
6 |
Correct |
59 ms |
19948 KB |
Output is correct |
7 |
Correct |
50 ms |
20164 KB |
Output is correct |
8 |
Correct |
52 ms |
20068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
16724 KB |
Output is correct |
2 |
Correct |
2332 ms |
20284 KB |
Output is correct |
3 |
Correct |
2009 ms |
20296 KB |
Output is correct |
4 |
Correct |
1776 ms |
20284 KB |
Output is correct |
5 |
Correct |
603 ms |
20300 KB |
Output is correct |
6 |
Correct |
916 ms |
20300 KB |
Output is correct |
7 |
Correct |
1667 ms |
20276 KB |
Output is correct |
8 |
Correct |
1662 ms |
20280 KB |
Output is correct |