#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 max_missed) {
int32_t ans = 0;
int32_t ptr1 = 0, ptr2 = 0;
int32_t missed = 0;
while(ptr1 < n && ptr2 < n) {
if(arr1[ptr1] == arr2[ptr2]) {
ans++;
ptr1++;
ptr2++;
} else {
missed++;
if(missed > max_missed)
return ans;
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], 2 * k);
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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
332 KB |
Output is correct |
2 |
Correct |
2 ms |
332 KB |
Output is correct |
3 |
Correct |
2 ms |
336 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
2008 KB |
Output is correct |
2 |
Correct |
125 ms |
12396 KB |
Output is correct |
3 |
Correct |
114 ms |
12400 KB |
Output is correct |
4 |
Correct |
114 ms |
12364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
114 ms |
13568 KB |
Output is correct |
2 |
Correct |
113 ms |
13628 KB |
Output is correct |
3 |
Correct |
124 ms |
13644 KB |
Output is correct |
4 |
Correct |
117 ms |
13604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
3 ms |
460 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
2 ms |
460 KB |
Output is correct |
5 |
Correct |
1 ms |
460 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
2 ms |
716 KB |
Output is correct |
3 |
Correct |
3 ms |
716 KB |
Output is correct |
4 |
Correct |
2 ms |
716 KB |
Output is correct |
5 |
Correct |
2 ms |
716 KB |
Output is correct |
6 |
Correct |
2 ms |
716 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
125 ms |
34760 KB |
Output is correct |
3 |
Correct |
129 ms |
34792 KB |
Output is correct |
4 |
Correct |
124 ms |
34848 KB |
Output is correct |
5 |
Correct |
130 ms |
34932 KB |
Output is correct |
6 |
Correct |
128 ms |
34796 KB |
Output is correct |
7 |
Correct |
125 ms |
34744 KB |
Output is correct |
8 |
Correct |
127 ms |
34912 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1612 KB |
Output is correct |
2 |
Correct |
633 ms |
482608 KB |
Output is correct |
3 |
Correct |
352 ms |
484028 KB |
Output is correct |
4 |
Correct |
448 ms |
484008 KB |
Output is correct |
5 |
Correct |
338 ms |
484004 KB |
Output is correct |
6 |
Correct |
352 ms |
484128 KB |
Output is correct |
7 |
Correct |
539 ms |
484040 KB |
Output is correct |
8 |
Correct |
396 ms |
484036 KB |
Output is correct |