#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 put(int k, int v) {
int h = hash(k), o;
for (o = eo[h]; o--; )
if (ek[h][o] == k) {
ev[h][o] = v;
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] = v;
}
int get(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--)
put(aa[i] + aa[j], 0);
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++) {
s = aa[i] + aa[j];
put(s, cnt = get(s) + 1);
if (cnt == 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;
}
Compilation message
tabletennis.c: In function 'put':
tabletennis.c:35:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
35 | if (o >= 2 && (o & o - 1) == 0) {
| ~~^~~
tabletennis.c: In function 'main':
tabletennis.c:57:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
57 | scanf("%d%d", &n, &k);
| ^~~~~~~~~~~~~~~~~~~~~
tabletennis.c:59:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | scanf("%d", &aa[i]);
| ^~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
15956 KB |
Output is correct |
2 |
Correct |
11 ms |
15956 KB |
Output is correct |
3 |
Correct |
10 ms |
16084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
16348 KB |
Output is correct |
2 |
Correct |
42 ms |
19916 KB |
Output is correct |
3 |
Correct |
43 ms |
19912 KB |
Output is correct |
4 |
Correct |
41 ms |
19924 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
41 ms |
19300 KB |
Output is correct |
2 |
Correct |
44 ms |
19844 KB |
Output is correct |
3 |
Correct |
47 ms |
19532 KB |
Output is correct |
4 |
Correct |
45 ms |
19852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
16716 KB |
Output is correct |
2 |
Correct |
12 ms |
16724 KB |
Output is correct |
3 |
Correct |
12 ms |
16712 KB |
Output is correct |
4 |
Correct |
12 ms |
16720 KB |
Output is correct |
5 |
Correct |
15 ms |
16700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
15956 KB |
Output is correct |
2 |
Correct |
14 ms |
16080 KB |
Output is correct |
3 |
Correct |
12 ms |
16336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
16576 KB |
Output is correct |
2 |
Correct |
13 ms |
16600 KB |
Output is correct |
3 |
Correct |
14 ms |
16724 KB |
Output is correct |
4 |
Correct |
13 ms |
16728 KB |
Output is correct |
5 |
Correct |
14 ms |
16628 KB |
Output is correct |
6 |
Correct |
12 ms |
16468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
16468 KB |
Output is correct |
2 |
Correct |
239 ms |
19852 KB |
Output is correct |
3 |
Correct |
120 ms |
19908 KB |
Output is correct |
4 |
Correct |
81 ms |
19876 KB |
Output is correct |
5 |
Correct |
131 ms |
19908 KB |
Output is correct |
6 |
Correct |
87 ms |
19532 KB |
Output is correct |
7 |
Correct |
81 ms |
19912 KB |
Output is correct |
8 |
Correct |
91 ms |
19940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
16712 KB |
Output is correct |
2 |
Execution timed out |
3060 ms |
46192 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |