제출 #675067

#제출 시각아이디문제언어결과실행 시간메모리
675067mouseyTable Tennis (info1cup20_tabletennis)C++14
87 / 100
3091 ms6344 KiB
//#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;
set <int> myset;

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()
{
  for(int l = 1; l <= k+1; l++)
  {
    for(int r = n+k; r >= n; r--)
    {
      if(l-1+n+k-r<=k)
      {
        myset.insert(a[l]+a[r]);
      }
    }
  }
  for(auto i: myset) v.pb(i);
  shuffle(v.begin(), v.end(), rng);
  for(int i = 0; i < (int) v.size(); i++)
  {
    if(ktra(v[i]))
    {
      print(v[i]);
      return;
    }
  }
}

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...