이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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";
}
# | 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... |