Submission #638143

#	Time	Username	Problem	Language	Result	Execution time	Memory
638143		Dec0Dedd	Table Tennis (info1cup20_tabletennis)	C++14	9 / 100	2249 ms	15292 KiB

tabletennis

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define pii pair<int, int>

const int N = 2e5+1;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

ll a[N], n, k, sz;

int rnd(int a, int b){ 
	return a+rng()%(b-a+1);
}

int cnt(int s) {
   gp_hash_table<int, bool, custom_hash> m;

   int res=0;
   for (int i=1; i<=sz; ++i) m[a[i]]=true;
   for (int i=1; i<=sz; ++i) {
      if (2*a[i] == s || m.find(s-a[i]) == m.end()) continue;
      ++res;
   }

   return res;
}

vector<int> genSeq(int s) {
   gp_hash_table<int, bool, custom_hash> m;
   vector<int> res;

   for (int i=1; i<=sz; ++i) m[a[i]]=true;
   for (int i=1; i<=sz; ++i) {
      if (2*a[i] == s || m.find(s-a[i]) == m.end()) continue;
      res.push_back(a[i]);
   }

   return res;
}

int main() {
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);
   cout.tie(NULL);
   
   cin>>n>>k;
   sz=n+k;

   for (int i=1; i<=sz; ++i) cin>>a[i];

   int lim=10;
   if (n <= k) lim=1e5;
   else if (n <= 2e3) lim=1e3;

   int x=0, s=0;
   for (int i=0; i<lim; ++i) {
      int l=rnd(1, n), r=rnd(1, n);
      while (l == r) l=rnd(1, n), r=rnd(1, n);
      int val=cnt(a[l]+a[r]);

      if (val > x) x=val, s=a[l]+a[r];
   }

   assert(x >= n);
   vector<int> v=genSeq(s);
   for (int i=0; i<n; ++i) cout<<v[i]<<" ";
   cout<<"\n"; 
}

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