Submission #675069

#	Time	Username	Problem	Language	Result	Execution time	Memory
675069		mousey	Table Tennis (info1cup20_tabletennis)	C++14	87 / 100	3086 ms	6340 KiB

tabletennis

  //#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);
    sort(v.begin(), v.end());
    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"; 
  }

• 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: 0 / 13