#include <bits/stdc++.h>
using namespace std;
//~ #define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
template<class T> bool chmin(T& a, const T& b) {return a>b? a=b, true:false;}
template<class T> bool chmax(T& a, const T& b) {return a<b? a=b, true:false;}
const int mod = 1e9+7, N = 2e5+5;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val)-1;}
int n, m, k;
int a[N];
bool check(vector<int> &v){
int n = v.size();
int t = v[0] + v[n-1];
for(int l=0,r=n-1;l<r;l++,r--){
if(v[l] + v[r] != t)return false;
}return true;
}
void O1_thing(vector<int> &a, int m){
int i, j;
bool ok = true;
int t = (a[1] + a[m-1]);
for(int l=1,r=m-1;l<r;l++,r--){
if(a[l] + a[r] != t)ok = false;
}
if(ok){
for(i=1;i<=m-1;i++)cout << a[i] << ' ' ;
cout << '\n';
exit(0);
}
ok = true;
t = (a[2] + a[m]);
for(int l=2,r=m;l<r;l++,r--){
if(a[l] + a[r] != t)ok = false;
}
if(ok){
for(i=2;i<=m;i++)cout << a[i] << ' ' ;
cout << '\n';
exit(0);
}
t = a[1] + a[m];
for(int l=2,r=m-1;l<r;l++,r--){
if(a[l] + a[r] != t){
vector<int> v;
for(i=1;i<=m;i++){
if(i==l)continue;
v.pb(a[i]);
}
if(check(v)){
for(auto x : v)cout << x << ' ' ;
cout << '\n';
exit(0);
}
v.clear();
for(i=1;i<=m;i++){
if(i==r)continue;
v.pb(a[i]);
}
if(check(v)){
for(auto x : v)cout << x << ' ' ;
cout << '\n';
exit(0);
}return;
}
}
}
void solve(int test_case){
int i, j;
cin >> n >> k;
m = n+k;
for(i=1;i<=m;i++){
cin >> a[i];
}
sort(a+1,a+m+1);
if(k == 1){
bool ok = true;
int t = (a[1] + a[m-1]);
for(int l=1,r=m-1;l<r;l++,r--){
if(a[l] + a[r] != t)ok = false;
}
if(ok){
for(i=1;i<=m-1;i++)cout << a[i] << ' ' ;
cout << '\n';
return;
}
ok = true;
t = (a[2] + a[m]);
for(int l=2,r=m;l<r;l++,r--){
if(a[l] + a[r] != t)ok = false;
}
if(ok){
for(i=2;i<=m;i++)cout << a[i] << ' ' ;
cout << '\n';
return;
}
t = a[1] + a[m];
for(int l=2,r=m-1;l<r;l++,r--){
if(a[l] + a[r] != t){
vector<int> v;
for(i=1;i<=m;i++){
if(i==l)continue;
v.pb(a[i]);
}
if(check(v)){
for(auto x : v)cout << x << ' ' ;
cout << '\n';
return;
}
v.clear();
for(i=1;i<=m;i++){
if(i==r)continue;
v.pb(a[i]);
}
if(check(v)){
for(auto x : v)cout << x << ' ' ;
cout << '\n';
return;
}
assert(false);
}
}
}else if(k > 2){
map<int,int> possible_sums_not;
for(i=1;i<=m;i++){
for(j=i+1;j<=m;j++){
possible_sums_not[a[i] + a[j]]++;
}
}
vector<pii> possible_sums;
for(auto [x,y] : possible_sums_not)possible_sums.pb({y,x});
sort(all(possible_sums));
reverse(all(possible_sums));
//~ mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//~ shuffle(all(possible_sums), rng);
for(auto [no_need, sum] : possible_sums){
unordered_map<int,int>cnt;
for(i=1;i<=m;i++){
cnt[a[i]]++;
}
int have = 0;
vector<int> v;
for(i=1;i<=m;i++){
if(cnt[a[i]] <= 0)continue;
if(a[i] >= sum)continue;
if(sum-a[i] == a[i]){
if(cnt[sum - a[i]] > 1){
cnt[sum - a[i]]--;
cnt[a[i]]--;
have++;
v.pb(a[i]);
v.pb(sum-a[i]);
}
}else if(cnt[sum - a[i]] > 0){
cnt[sum - a[i]]--;
cnt[a[i]]--;
have++;
v.pb(a[i]);
v.pb(sum-a[i]);
}
}
//~ cout << sum << ' ' << have << '\n';
if(have >= n/2){
sort(v.begin(), v.begin() + n);
for(i=0;i<n;i++)cout << v[i] << ' ' ;
cout << '\n';
return;
}
}
}else {
{
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
shuffle(a+1,a+m+1, rng);
for(i=1;i<=min(1200,m);i++){
vector<int> v = {0};
for(j=1;j<=m;j++){
if(j == i)continue;
v.pb(a[j]);
}assert((int)v.size() == m-1);
O1_thing(v, m-1);
}
}
}
return;
}
/*
4 1
2 4 8 6 10
*/
signed main(){
FASTIO;
//~ #define MULTITEST 1
#if MULTITEST
int _T;
cin >> _T;
for(int T_CASE = 1; T_CASE <= _T; T_CASE++)
solve(T_CASE);
#else
solve(1);
#endif
return 0;
}
Compilation message
tabletennis.cpp: In function 'void O1_thing(std::vector<int>&, int)':
tabletennis.cpp:26:9: warning: unused variable 'j' [-Wunused-variable]
26 | int i, j;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
876 KB |
Output is correct |
| 2 |
Correct |
41 ms |
2412 KB |
Output is correct |
| 3 |
Correct |
36 ms |
2540 KB |
Output is correct |
| 4 |
Correct |
35 ms |
2412 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
31 ms |
3304 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1004 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1260 KB |
Output is correct |
| 3 |
Correct |
4 ms |
1260 KB |
Output is correct |
| 4 |
Correct |
4 ms |
1260 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
127 ms |
3176 KB |
Output is correct |
| 3 |
Correct |
1620 ms |
104340 KB |
Output is correct |
| 4 |
Correct |
964 ms |
85324 KB |
Output is correct |
| 5 |
Correct |
111 ms |
3232 KB |
Output is correct |
| 6 |
Correct |
112 ms |
1516 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Execution timed out |
3095 ms |
326040 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
5860 KB |
Output is correct |
| 2 |
Execution timed out |
3090 ms |
481800 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
