#include <bits/stdc++.h>
#define endl '\n'
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define int ll
typedef long long ll;
using namespace std;
const int N = 15e4 + 10, mod = 1e9 + 7;
int n, k, a[N];
map<int, bool> vis;
map<int, vector<pair<int, int> > > mp;
void solve() {
int ch1 = a[0] + a[n+k-1], ch2 = a[0] + a[n+k-2], ch3 = a[1] + a[n+k-1];
int cnt1 = 0, cnt2 = 0, cnt3 = 0;
for(int i = 0; i < n + k; i++) {
if(vis[ch1 - a[i]]) cnt1++;
if(vis[ch2 - a[i]]) cnt2++;
if(vis[ch3 - a[i]]) cnt3++;
}
int num = 0;
if(cnt1 >= cnt2 && cnt1 >= cnt3) num = ch1;
else if(cnt2 >= cnt1 && cnt2 >= cnt3) num = ch2;
else num = ch3;
int dont = a[n+k-1];
for(int i = 0; i < n + k; i++) {
if(vis[num - a[i]]) cout << a[i] << ' ';
}
return;
}
// 2 + 2 = 4
// 4 + 2 = 6
void solve1() {
vector<int> v;
int cnt[100];
for(int i = 0; i < 100; i++) cnt[i] = 0;
if(n + k == 4) for(int i = 0; i < n + k; i++) v.push_back(a[i]);
else {
v.push_back(a[0]);
v.push_back(a[1]);
v.push_back(a[2]);
v.push_back(a[n+k-1]);
v.push_back(a[n+k-2]);
v.push_back(a[n+k-3]);
}
set<int> s;
for(int i = 0; i < v.size(); i++) {
for(int j = 0; j < v.size(); j++) {
s.insert(v[i] + v[j]);
}
}
vector<int> nums;
for(auto it : s) nums.push_back(it);
int num = 0, cur = 0;
for(int i = 0; i < n + k; i++) {
for(int j = 0; j < nums.size(); j++) {
if(vis[nums[j] - a[i]]) cnt[j]++;
if(cnt[j] > cur) {
cur = cnt[j];
num = nums[j];
}
}
}
set<pair<int, int> > ans;
for(int i = 0; i < n + k; i++) {
if(vis[num - a[i]]) ans.insert({min(num-a[i], a[i]), max(num-a[i], a[i])});
}
vector<int> fin;
for(auto it : ans) {
if(fin.size() == n) break;
fin.push_back(it.first);
fin.push_back(it.second);
}
sort(fin.begin(), fin.end());
for(int it : fin) cout << it << ' ';
return;
}
void solve2() {
set<int> v;
int cnt[1000];
for(int i = 0; i < 1000; i++) cnt[i] = 0;
for(int i = 0; i < k + 1; i++) if(i < n + k) v.insert(a[i]);
for(int i = n + k - 1; i >= (n + k - 1) - k; i--) if(i >= 0) v.insert(a[i]);
set<int> s;
for(auto i : v) {
for(auto j : v) {
s.insert(i + j);
}
}
vector<int> nums;
for(auto it : s) nums.push_back(it);
int num = 0, cur = 0;
for(int i = 0; i < n + k; i++) {
for(int j = 0; j < nums.size(); j++) {
if(vis[nums[j] - a[i]]) cnt[j]++;
if(cnt[j] > cur) {
cur = cnt[j];
num = nums[j];
}
}
}
set<pair<int, int> > ans;
for(int i = 0; i < n + k; i++) {
if(vis[num - a[i]]) ans.insert({min(num-a[i], a[i]), max(num-a[i], a[i])});
}
vector<int> fin;
for(auto it : ans) {
if(fin.size() == n) break;
fin.push_back(it.first);
fin.push_back(it.second);
}
sort(fin.begin(), fin.end());
for(int it : fin) cout << it << ' ';
return;
}
signed main() {
FAST;
cin >> n >> k;
int num = 0;
for(int i = 0; i < n + k; i++) {
cin >> a[i];
vis[a[i]] = 1;
}
if(k == 1) {
solve();
return 0;
}
if(k == 2) {
solve1();
return 0;
}
if(k <= 20) {
solve2();
return 0;
}
for(int i = 0; i < n + k - 1; i++) {
for(int j = i + 1; j < n + k; j++) {
mp[a[i] + a[j]].push_back({a[i], a[j]});
if(mp[a[i] + a[j]].size() >= n / 2) num = a[i] + a[j];
}
}
vector<int> v;
int i = 0;
while(v.size() < n && i < mp[num].size()) {
v.push_back(mp[num][i].first);
v.push_back(mp[num][i].second);
i++;
}
sort(v.begin(), v.end());
for(auto it : v) {
cout << it << ' ';
}
}
Compilation message
tabletennis.cpp: In function 'void solve()':
tabletennis.cpp:23:9: warning: unused variable 'dont' [-Wunused-variable]
23 | int dont = a[n+k-1];
| ^~~~
tabletennis.cpp: In function 'void solve1()':
tabletennis.cpp:45:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
tabletennis.cpp:46:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int j = 0; j < v.size(); j++) {
| ~~^~~~~~~~~~
tabletennis.cpp:54:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int j = 0; j < nums.size(); j++) {
| ~~^~~~~~~~~~~~~
tabletennis.cpp:68:23: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
68 | if(fin.size() == n) break;
| ~~~~~~~~~~~^~~~
tabletennis.cpp: In function 'void solve2()':
tabletennis.cpp:92:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for(int j = 0; j < nums.size(); j++) {
| ~~^~~~~~~~~~~~~
tabletennis.cpp:106:23: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
106 | if(fin.size() == n) break;
| ~~~~~~~~~~~^~~~
tabletennis.cpp: In function 'int main()':
tabletennis.cpp:137:39: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
137 | if(mp[a[i] + a[j]].size() >= n / 2) num = a[i] + a[j];
| ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
tabletennis.cpp:142:20: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
142 | while(v.size() < n && i < mp[num].size()) {
| ~~~~~~~~~^~~
tabletennis.cpp:142:29: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | while(v.size() < n && i < mp[num].size()) {
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
772 KB |
Output is correct |
| 2 |
Correct |
2 ms |
596 KB |
Output is correct |
| 3 |
Correct |
2 ms |
596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
1904 KB |
Output is correct |
| 2 |
Correct |
143 ms |
31048 KB |
Output is correct |
| 3 |
Correct |
153 ms |
31024 KB |
Output is correct |
| 4 |
Correct |
141 ms |
31088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
802 ms |
168428 KB |
Output is correct |
| 2 |
Correct |
1090 ms |
196644 KB |
Output is correct |
| 3 |
Correct |
820 ms |
182864 KB |
Output is correct |
| 4 |
Correct |
1036 ms |
196336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1236 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2004 KB |
Output is correct |
| 3 |
Correct |
5 ms |
2004 KB |
Output is correct |
| 4 |
Correct |
5 ms |
2004 KB |
Output is correct |
| 5 |
Correct |
6 ms |
2004 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
980 KB |
Output is correct |
| 2 |
Correct |
163 ms |
32224 KB |
Output is correct |
| 3 |
Correct |
501 ms |
112996 KB |
Output is correct |
| 4 |
Correct |
344 ms |
80124 KB |
Output is correct |
| 5 |
Correct |
243 ms |
32956 KB |
Output is correct |
| 6 |
Correct |
44 ms |
4044 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
980 KB |
Output is correct |
| 2 |
Runtime error |
50 ms |
21824 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
10316 KB |
Output is correct |
| 2 |
Runtime error |
51 ms |
21880 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
