Submission #675139

#	Time	Username	Problem	Language	Result	Execution time	Memory
675139		mousey	Table Tennis (info1cup20_tabletennis)	C++14	100 / 100	422 ms	43324 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;
  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"; 
  }

• 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