//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define vll vector<ll>
#define vllp vector<pair<ll, ll> >
#define vi vector <int>
#define vip vector <pair <int, int> >
#define db double
#define ldb long double
#define pdb pair <double, double>
#define YES cout<<"Yes"
#define NO cout<<"No"
#define nl cout<<"\n"
#define vv vector <vector <ll> >
#define pll pair <ll, ll>
#define pi pair <int, int>
#define pb push_back
#define f first
#define s second
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod=1e9+7;
const ll modx=998244353;
const double eps=1e-9;
const ll INF=2e9;
const ll INFINF=9e18;
const int N=150000, K=400;
int n, k, a[N+K+5];
vi v, ans;
map <int, int> dem;
void input()
{
cin >> n >> k;
for(int i = 1; i <= n+k; i++)
{
cin >> a[i];
}
}
bool ktra(int sum)
{
int l=1, r=n+k;
int cnt=0;
while(l<r)
{
if(a[l]+a[r]==sum)
{
cnt+=2;
l++;
r--;
}
else if(a[l]+a[r]>sum) r--;
else l++;
}
if(cnt>=n) return true;
return false;
}
void print(int sum)
{
int l=1, r=n+k;
while(l<r)
{
if(a[l]+a[r]==sum)
{
if((int) ans.size()<n) ans.pb(a[l]), ans.pb(a[r]);
l++;
r--;
}
else if(a[l]+a[r]>sum) r--;
else l++;
}
sort(ans.begin(), ans.end());
for(auto i: ans) cout << i << " ";
}
void solve()
{
if(n+k>=4*k)
{
for(int l = 1; l <= min(2*k, n+k); l++)
{
for(int r = n+k; r >= max(n-k, 1ll); r--)
{
if(l>=r) continue;
else
{
// cout << l << " " << r << "\n";
dem[a[l]+a[r]]++;
}
}
}
for(auto i: dem)
{
// cout << i.f << " " << i.s << "\n";
if(i.s<k) continue;
else
{
if(ktra(i.f))
{
print(i.f);
return;
}
}
}
}
else
{
for(int l = 1; l <= k+1; l++)
{
for(int r = n+k; r >= n; r--)
{
if(l-1+n+k-r<=k)
{
if(ktra(a[l]+a[r]))
{
print(a[l]+a[r]);
return;
}
}
else break;
}
}
}
}
signed main()
{
// auto start_time = chrono::high_resolution_clock::now();
// #ifdef ONLINE_JUDGE
// freopen("f.in", "r", stdin);
// #endif
// freopen("f.in", "r", stdin);
// freopen("kek.out", "w", stdout);
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int t=1;
// cin >> t;
for(int i = 1; i <= t; i++)
{
input();
solve();
}
// auto end_time = chrono::high_resolution_clock::now();
// double duration = chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count();
// cout << "\n[ " << duration << " ms ]\n";
}
# |
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 |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
984 KB |
Output is correct |
2 |
Correct |
44 ms |
4208 KB |
Output is correct |
3 |
Correct |
58 ms |
4236 KB |
Output is correct |
4 |
Correct |
36 ms |
4228 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
4244 KB |
Output is correct |
2 |
Correct |
48 ms |
4304 KB |
Output is correct |
3 |
Correct |
49 ms |
4232 KB |
Output is correct |
4 |
Correct |
44 ms |
4232 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
232 KB |
Output is correct |
4 |
Correct |
3 ms |
324 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
448 KB |
Output is correct |
5 |
Correct |
2 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
45 ms |
4312 KB |
Output is correct |
3 |
Correct |
42 ms |
4268 KB |
Output is correct |
4 |
Correct |
39 ms |
4208 KB |
Output is correct |
5 |
Correct |
37 ms |
4260 KB |
Output is correct |
6 |
Correct |
44 ms |
4216 KB |
Output is correct |
7 |
Correct |
48 ms |
4228 KB |
Output is correct |
8 |
Correct |
36 ms |
4296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
212 KB |
Output is correct |
2 |
Correct |
422 ms |
41040 KB |
Output is correct |
3 |
Correct |
369 ms |
43324 KB |
Output is correct |
4 |
Correct |
260 ms |
37900 KB |
Output is correct |
5 |
Correct |
150 ms |
13408 KB |
Output is correct |
6 |
Correct |
78 ms |
4604 KB |
Output is correct |
7 |
Correct |
262 ms |
33484 KB |
Output is correct |
8 |
Correct |
212 ms |
36540 KB |
Output is correct |