#include <stdio.h>
#include <stdlib.h>
#define N 150000
#define K 400
#define M 1000000
#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;
}
}
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 |
49 ms |
78676 KB |
Output is correct |
2 |
Correct |
53 ms |
78520 KB |
Output is correct |
3 |
Correct |
50 ms |
78652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
54 ms |
78932 KB |
Output is correct |
2 |
Correct |
83 ms |
84812 KB |
Output is correct |
3 |
Correct |
82 ms |
84668 KB |
Output is correct |
4 |
Correct |
82 ms |
84760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
76 ms |
81024 KB |
Output is correct |
2 |
Correct |
83 ms |
84760 KB |
Output is correct |
3 |
Correct |
79 ms |
81340 KB |
Output is correct |
4 |
Correct |
81 ms |
84736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
82380 KB |
Output is correct |
2 |
Correct |
53 ms |
82412 KB |
Output is correct |
3 |
Correct |
52 ms |
82368 KB |
Output is correct |
4 |
Correct |
52 ms |
82416 KB |
Output is correct |
5 |
Correct |
60 ms |
82468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
49 ms |
78588 KB |
Output is correct |
2 |
Correct |
49 ms |
78636 KB |
Output is correct |
3 |
Correct |
49 ms |
78940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
50 ms |
79684 KB |
Output is correct |
2 |
Correct |
52 ms |
80160 KB |
Output is correct |
3 |
Correct |
56 ms |
82484 KB |
Output is correct |
4 |
Correct |
53 ms |
82376 KB |
Output is correct |
5 |
Correct |
51 ms |
80412 KB |
Output is correct |
6 |
Correct |
50 ms |
79316 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
49 ms |
79692 KB |
Output is correct |
2 |
Correct |
477 ms |
84712 KB |
Output is correct |
3 |
Correct |
169 ms |
84712 KB |
Output is correct |
4 |
Correct |
117 ms |
84580 KB |
Output is correct |
5 |
Correct |
158 ms |
84704 KB |
Output is correct |
6 |
Correct |
116 ms |
81436 KB |
Output is correct |
7 |
Correct |
119 ms |
84812 KB |
Output is correct |
8 |
Correct |
121 ms |
84548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
58 ms |
82400 KB |
Output is correct |
2 |
Execution timed out |
3072 ms |
83168 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |