제출 #638663

#제출 시각아이디문제언어결과실행 시간메모리
638663Dec0DeddTable Tennis (info1cup20_tabletennis)C++14
72 / 100
3063 ms311020 KiB
#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 = 45; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int rnd(int a, int b){ return a+rng()%(b-a+1); } int a[N], n, k, sz; gp_hash_table<int, int> cnt; gp_hash_table<int, bool> m; void add(int i) { for (int j=1; j<=sz; ++j) { if (j != i) ++cnt[a[i]+a[j]]; } } int num(int s) { int res=0; 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> gen(int s) { 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]; for (int i=1; i<=sz; ++i) m[a[i]]=true; vector<int> tmp; if (sz <= 2000) { for (int i=1; i<=sz; ++i) { for (int j=i+1; j<=sz; ++j) ++cnt[a[i]+a[j]]; } int mx=0, val=0; for (auto u : cnt) { if (u.second > val) val=u.second, mx=u.first; } tmp.push_back(mx); } else { vector<int> r; for (int i=1; i<=sz; ++i) r.push_back(i); shuffle(r.begin(), r.end(), rng); for (int i=0; i<min(sz, K); ++i) add(r[i]); for (auto u : cnt) { if (u.second >= 33) tmp.push_back(u.first); } } vector<int> x; for (auto u : tmp) { if (num(u) >= n) { x=gen(u); break; } } assert((int)x.size() >= n); for (auto u : x) cout<<u<<" "; cout<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...