Submission #1365291

#TimeUsernameProblemLanguageResultExecution timeMemory
1365291vjudge1Table Tennis (info1cup20_tabletennis)C++20
52 / 100
219 ms42132 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pu push_back
int main(){
  ll n, k;
  cin>>n>>k;
  ll b[n+k+10];
  for(ll i = 1; i <= n+k; i++) cin>>b[i];
  vector<bool> ans(n+k+1, false);
  if(n+k <= 4*k){
    for(ll l = 1; l <= min(n+k, 2LL*k); l++){
      for(ll r = n+k; r >= max(1LL, n-k); r--){
        if(l-1+n+k-r > k) continue;
        ans[l] = true;
        ans[r] = true;
        ll sum = b[l]+b[r];
        ll buang = l-1+n+k-r;
        ll l2 = l+1, r2 = r-1;
        while(l2 <= r2){
          if(b[l2]+b[r2] == sum){ 
            ans[l2] = true, ans[r2] = true;
            l2++, r2--;
            continue;
          }
          if(b[l2]+b[r2] < sum) l2++, buang++;
          else r2--, buang++;
        }
        if(k >= buang && (k-buang)%2 == 0) {
           buang = k - buang;
           for (ll i = 1, j = 1; i <= n + k, j + j <= buang; i++) {
               if (ans[i]) {
                   ans[i] = false;
                   j++;
               }
           }
           for (ll i = n + k, j = 1; i >= 1, j + j <= buang; i--) {
               if (ans[i]) {
                   ans[i] = false;
                   j++;
               }
           }
           for(ll i = 1; i <= n+k; i++){
             if(ans[i]) cout<<b[i]<<" ";
           }
           return 0;
        }
        for(ll i = 1; i <= n+k; i++) ans[i] = false;
      }
    }
  }
  else{
    map<ll, ll> freq;
    for(ll i = 1; i <= 2*k; i++){
      for(ll j = n-k+1; j <= n+k; j++){
        freq[b[i]+b[j]]++;
      }
    }
    for(auto [x, _] : freq){
      if( _ >= k){
        ll sum = x;
        ll left = 1 , right = n+k;
        ll buang = left-1+n+k-right;
        while(left <= right){
          if(b[left]+b[right] == sum){
            ans[left] = true;
            ans[right] = true;
            left++, right--;
            continue;
          }
          if(b[left]+b[right] < sum){
            left++, buang++;
          }
          else right--, buang++;
        }
        if(k >= buang && (k-buang)%2 == 0){
          buang = k - buang;
          for (ll i = 1, j = 1; i <= n + k, j + j <= buang; i++) {
              if (ans[i]) {
                  ans[i] = false;
                  j++;
              }
          }
          for (ll i = n + k, j = 1; i >= 1, j + j <= buang; i--) {
              if (ans[i]) {
                  ans[i] = false;
                  j++;
              }
          }
          for(ll i = 1; i <= n+k; i++){
            if(ans[i]) cout<<b[i]<<" ";
          }
          return 0;
        }
      }
    }
  }
} //test
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...