#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>
#define BASE 1'000'000'005
#define MOD 1'000'000'007
int32_t* base_powers;
int32_t get_hash(int32_t* hashes, int32_t start, int32_t len) {
return (hashes[start + len] - ((int64_t)hashes[start] * base_powers[len]) % MOD + MOD) % MOD;
}
int32_t get_matches(int32_t n, int32_t* arr1, int32_t* arr2, int32_t max_missed,
int32_t* hashes_left, int32_t* hashes_right) {
int32_t ans = 0;
int32_t ptr1 = 0, ptr2 = 0;
int32_t missed = 0;
while(ptr1 < n && ptr2 < n) {
if(arr1[ptr1] == arr2[ptr2]) {
int32_t left = 1, right = n - std::max(ptr1, ptr2) + 1;
while(right - left > 1) {
int32_t m = (left + right) / 2;
if(get_hash(hashes_left, ptr1, m) == get_hash(hashes_right, ptr2, m))
left = m;
else
right = m;
}
ans += left;
ptr1 += left;
ptr2 += left;
} else {
missed++;
if(missed > max_missed)
return ans;
if(arr1[ptr1] < arr2[ptr2])
ptr1++;
else
ptr2++;
}
}
return ans;
}
int main() {
base_powers = new int32_t[200'000];
base_powers[0] = 1;
for(int32_t i = 1; i < 200'000; i++)
base_powers[i] = ((int64_t)base_powers[i - 1] * BASE) % MOD;
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];
int32_t** hashes_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];
hashes_start[i] = new int32_t[n + 1];
hashes_start[i][0] = 0;
for(int32_t j = 1; j <= n; j++)
hashes_start[i][j] = (hashes_start[i][j - 1] * BASE + per_start[i][j - 1] + 1'000'000'000) % MOD;
}
int32_t** per_end = new int32_t*[k + 1];
int32_t** hashes_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);
hashes_end[i] = new int32_t[n + 1];
hashes_end[i][0] = 0;
for(int32_t j = 1; j <= n; j++)
hashes_end[i][j] = (hashes_end[i][j - 1] * BASE + per_end[i][j - 1] + 1'000'000'000) % MOD;
}
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,
hashes_start[i], hashes_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 |
3 ms |
1228 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1228 KB |
Output is correct |
| 3 |
Correct |
4 ms |
1228 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
3232 KB |
Output is correct |
| 2 |
Correct |
174 ms |
15756 KB |
Output is correct |
| 3 |
Correct |
165 ms |
15800 KB |
Output is correct |
| 4 |
Correct |
154 ms |
15844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
157 ms |
18104 KB |
Output is correct |
| 2 |
Correct |
157 ms |
18108 KB |
Output is correct |
| 3 |
Correct |
164 ms |
18360 KB |
Output is correct |
| 4 |
Correct |
159 ms |
18064 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1228 KB |
Output is correct |
| 2 |
Correct |
10 ms |
1412 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1348 KB |
Output is correct |
| 4 |
Correct |
5 ms |
1356 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
972 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1100 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1092 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1868 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1864 KB |
Output is correct |
| 4 |
Correct |
4 ms |
1864 KB |
Output is correct |
| 5 |
Correct |
4 ms |
1868 KB |
Output is correct |
| 6 |
Correct |
4 ms |
1868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
211 ms |
60608 KB |
Output is correct |
| 3 |
Correct |
204 ms |
60600 KB |
Output is correct |
| 4 |
Correct |
209 ms |
60672 KB |
Output is correct |
| 5 |
Correct |
219 ms |
60480 KB |
Output is correct |
| 6 |
Correct |
202 ms |
60588 KB |
Output is correct |
| 7 |
Correct |
211 ms |
60748 KB |
Output is correct |
| 8 |
Correct |
200 ms |
60524 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
3788 KB |
Output is correct |
| 2 |
Correct |
1675 ms |
956136 KB |
Output is correct |
| 3 |
Correct |
1152 ms |
955836 KB |
Output is correct |
| 4 |
Correct |
1351 ms |
955876 KB |
Output is correct |
| 5 |
Correct |
1138 ms |
955896 KB |
Output is correct |
| 6 |
Correct |
1150 ms |
955884 KB |
Output is correct |
| 7 |
Correct |
1452 ms |
955924 KB |
Output is correct |
| 8 |
Correct |
1141 ms |
955808 KB |
Output is correct |
