This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 = 401;
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<K; ++i) {
int x=rnd(1, sz); add(x);
}
vector<pair<int, int>> tmp;
for (auto u : cnt) tmp.push_back({u.second, u.first});
sort(tmp.begin(), tmp.end());
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";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |