#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <unordered_set>
#include <sstream>
#include <cstring>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <random>
#include <cfloat>
#include <chrono>
#include <bitset>
#include <complex>
#include <immintrin.h>
#include <cassert>
int32_t get_matches(int32_t n, int32_t* arr1, int32_t* arr2) {
int32_t ans = 0;
int32_t ptr1 = 0, ptr2 = 0;
while(ptr1 < n && ptr2 < n) {
if(arr1[ptr1] == arr2[ptr2]) {
ans++;
ptr1++;
ptr2++;
} else if(arr1[ptr1] < arr2[ptr2])
ptr1++;
else
ptr2++;
}
return ans;
}
int main() {
int32_t n, k;
std::cin >> n >> k;
n += k;
int32_t* arr = new int32_t[n];
for(int32_t i = 0; i < n; i++)
std::cin >> arr[i];
int32_t** per_start = new int32_t*[k + 1];
for(int32_t i = 0; i <= k; i++) {
per_start[i] = new int32_t[n];
for(int32_t j = 0; j < n; j++)
per_start[i][j] = arr[j] - arr[i];
}
int32_t** per_end = new int32_t*[k + 1];
for(int32_t i = 0; i <= k; i++) {
per_end[i] = new int32_t[n];
for(int32_t j = 0; j < n; j++)
per_end[i][j] = arr[n - i - 1] - arr[j];
std::reverse(per_end[i], per_end[i] + n);
}
for(int32_t i = 0; i <= k; i++)
for(int32_t j = 0;j <= k; j++) {
int32_t matches = get_matches(n, per_start[i], per_end[j]);
if(matches >= n - k) {
int32_t true_sum = arr[i] + arr[n - j - 1];
std::map<int32_t, int32_t> freq;
for(int32_t p = 0; p < n; p++)
freq[arr[p]]++;
std::vector<int32_t> ans;
for(int32_t p = 0; p < n; p++)
if(arr[p] * 2 < true_sum && freq[true_sum - arr[p]] > 0) {
ans.push_back(arr[p]);
ans.push_back(true_sum - arr[p]);
freq[true_sum - arr[p]]--;
} else if(arr[p] * 2 == true_sum && freq[true_sum - arr[p]] > 1) {
ans.push_back(arr[p]);
ans.push_back(true_sum - arr[p]);
freq[true_sum - arr[p]]-=2;
}
ans.resize(n - k);
std::sort(ans.begin(), ans.end());
for(int32_t p = 0; p < n - k; p++)
std::cout << ans[p] << " ";
return 0;
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
460 KB |
Output is correct |
2 |
Correct |
2 ms |
412 KB |
Output is correct |
3 |
Correct |
2 ms |
448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
2136 KB |
Output is correct |
2 |
Correct |
122 ms |
13944 KB |
Output is correct |
3 |
Correct |
114 ms |
13792 KB |
Output is correct |
4 |
Correct |
112 ms |
13908 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
118 ms |
14164 KB |
Output is correct |
2 |
Correct |
115 ms |
15036 KB |
Output is correct |
3 |
Correct |
118 ms |
15056 KB |
Output is correct |
4 |
Correct |
146 ms |
15080 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
5 ms |
420 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
3 ms |
416 KB |
Output is correct |
5 |
Correct |
1 ms |
420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
3 ms |
716 KB |
Output is correct |
3 |
Correct |
2 ms |
716 KB |
Output is correct |
4 |
Correct |
2 ms |
716 KB |
Output is correct |
5 |
Correct |
3 ms |
720 KB |
Output is correct |
6 |
Correct |
3 ms |
716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
514 ms |
36300 KB |
Output is correct |
3 |
Correct |
151 ms |
36276 KB |
Output is correct |
4 |
Correct |
205 ms |
36212 KB |
Output is correct |
5 |
Correct |
128 ms |
36184 KB |
Output is correct |
6 |
Correct |
170 ms |
36240 KB |
Output is correct |
7 |
Correct |
172 ms |
36280 KB |
Output is correct |
8 |
Correct |
139 ms |
36260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1612 KB |
Output is correct |
2 |
Execution timed out |
3111 ms |
474756 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |