Submission #1317984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317984		ayaz	Table Tennis (info1cup20_tabletennis)	C++20	100 / 100	80 ms	20468 KiB

tabletennis

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define all(x) (x).begin(), (x).end()
#define isz(x) (int)(x.size())
#define int ll

const int sz = 500200, inf = 1000000000;

int a[sz], n, k;
void check(int sum) {
  vector<pair<int, int>> v;
  int L = 1, R = n + k;
  while (L <= R && isz(v) < n / 2) {
    if(a[L] + a[R] == sum){
      v.push_back({L, R});
      L++;
      R--;
    }
    else if(a[L] + a[R] > sum) {
      R--;
    } else {
      L++;
    }
  }
  if (isz(v) == n / 2) {
    vector<int> ans;
    for (auto [x, y] : v) {
      ans.push_back(x);
      ans.push_back(y);
    }
    sort(all(ans));
    for (auto i : ans) {
      cout << a[i] << ' ';
    }
    exit(0);
  }
}
void run_case(int tc) {
  cin >> n >> k;
  for (int i = 1; i <= n + k; i++) {
    cin >> a[i];
  }
  map<int, int> cnt;
  // cemin sayi maximumdursa onu duzeltmek lazimdir
  // butun cemlere baxa bilmerik amma...
  // Randoma inanaq!
  for (int l = 0; l <= k; l++) {
    for (int r = 0; r <= k; r++) {
      int mn = a[l + 1], mx = a[n + k - r]; 
      cnt[mn + mx]++;
    }
  }
  vector<int> sum[n + 1];
  for (auto &[x, y] : cnt) sum[y].push_back(x);
  for (int i = n; i >= 1; i--) {
    if (sum[i].empty()) continue;

    for (auto &sm : sum[i]) {
      check(sm);
    }
  }
}
void precompute() {}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
#ifdef LOCAL
  // freopen("err.log", "w", stderr);
#endif
  precompute();
  int t = 1; // cin >> t;
  for (int tc = 1; tc <= t; tc++) run_case(tc);
}

• Subtask 1: 11 / 11
• Subtask 2: 9 / 9
• Subtask 3: 14 / 14
• Subtask 4: 15 / 15
• Subtask 5: 9 / 9
• Subtask 6: 14 / 14
• Subtask 7: 15 / 15
• Subtask 8: 13 / 13