Submission #638655

#	Time	Username	Problem	Language	Result	Execution time	Memory
638655		Dec0Dedd	Table Tennis (info1cup20_tabletennis)	C++14	11 / 100	3109 ms	594980 KiB

tabletennis

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

using namespace std;
using namespace __gnu_pbds;

const int N = 2e5+10;
const int K = 100;

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);
    }
};

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

int a[N], n, k, sz;
gp_hash_table<int, int, custom_hash> cnt;

void add(int i) {
   for (int j=1; j<=sz; ++j) ++cnt[a[i]+a[j]];
}

vector<int> gen(int s) {
   gp_hash_table<int, bool, custom_hash> m;
   for (int i=1; i<=sz; ++i) m[a[i]]=true;
   vector<int> res;

   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];

   vector<int> r;
   for (int i=1; i<=n; ++i) r.push_back(i);
   shuffle(r.begin(), r.end(), rng);

   for (int i=0; i<min(sz, K); ++i) add(r[i]);
   vector<pair<int, int>> tmp;
   for (auto u : cnt) tmp.push_back({u.second, u.first});
   sort(tmp.begin(), tmp.end(), greater<pair<int, int>>());

   vector<int> x;
   for (auto u : tmp) {
      x=gen(u.second);
      if ((int)x.size() >= n) break;
   }

   assert((int)x.size() >= n);
   for (auto u : x) cout<<u<<" ";
   cout<<"\n";
}

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