# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
364055 | 2021-02-08T06:57:51 Z | stefdasca | Table Tennis (info1cup20_tabletennis) | C++14 | 714 ms | 160016 KB |
#include<bits/stdc++.h> #define god dimasi5eks #pragma GCC optimize("Ofast") #define fi first #define se second #define pb push_back #define pf push_front #define mod 1000000007 #define dancila 3.14159265359 #define eps 1e-9 // #define fisier 1 using namespace std; typedef long long ll; int n, k, skills[200002]; unordered_map<int, int> frq; bitset<2000000002>vv; int main() { #ifdef fisier ifstream f("input.in"); ofstream g("output.out"); #endif ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> k; for(int i = 1; i <= n+k; ++i) cin >> skills[i]; int smm = 0; for(int i = 1; i <= k+1; ++i) for(int j = n - (i-1); j <= min(n+k, n+k+k - (i-1)); ++j) { if(i >= j) continue; frq[skills[i] + skills[j]]++; vv[skills[i] + skills[j]] = 1; if(frq[skills[i] + skills[j]] == n/2) { smm = skills[i] + skills[j]; break; } } for(int i = k+2; i <= min(20000, n/2+k); ++i) if(!smm) for(int j = n - (i-1); j <= min(n+k, n+k+k - (i-1)); ++j) { if(i >= j) continue; if(vv[skills[i] + skills[j]]) { if(frq[skills[i] + skills[j]] + (n/2+k) - i + 1 < n/2) vv[skills[i] + skills[j]] = 0; else { ++frq[skills[i] + skills[j]]; if(frq[skills[i] + skills[j]] == n/2) { smm = skills[i] + skills[j]; break; } } } } if(!smm) { unordered_map<int, int> ::iterator it; for(it = frq.begin(); it != frq.end(); ++it) if(smm == 0) smm = it -> first; else if(it -> second > frq[smm]) smm = it -> first; } int Rp = n+k; vector<int> ans; for(int i = 1; i <= n+k; ++i) { while(Rp > 0 && skills[i] + skills[Rp] > smm) --Rp; if(Rp > i && skills[i] + skills[Rp] == smm) { ans.pb(skills[Rp]); ans.pb(skills[i]); --Rp; } if(ans.size() == n) break; } sort(ans.begin(), ans.end()); for(int i = 0; i < ans.size(); ++i) cout << ans[i] << " "; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 492 KB | Output is correct |
2 | Correct | 1 ms | 492 KB | Output is correct |
3 | Correct | 1 ms | 492 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 1080 KB | Output is correct |
2 | Correct | 42 ms | 4712 KB | Output is correct |
3 | Correct | 41 ms | 4584 KB | Output is correct |
4 | Correct | 50 ms | 4712 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 43 ms | 4584 KB | Output is correct |
2 | Correct | 42 ms | 4712 KB | Output is correct |
3 | Correct | 43 ms | 4712 KB | Output is correct |
4 | Correct | 41 ms | 4712 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 19180 KB | Output is correct |
2 | Correct | 2 ms | 1004 KB | Output is correct |
3 | Correct | 7 ms | 9068 KB | Output is correct |
4 | Correct | 3 ms | 3180 KB | Output is correct |
5 | Correct | 8 ms | 7276 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 492 KB | Output is correct |
3 | Correct | 1 ms | 876 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 1388 KB | Output is correct |
2 | Correct | 4 ms | 512 KB | Output is correct |
3 | Correct | 2 ms | 748 KB | Output is correct |
4 | Correct | 2 ms | 620 KB | Output is correct |
5 | Correct | 4 ms | 876 KB | Output is correct |
6 | Correct | 3 ms | 1004 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 1388 KB | Output is correct |
2 | Correct | 44 ms | 4712 KB | Output is correct |
3 | Correct | 43 ms | 4968 KB | Output is correct |
4 | Correct | 68 ms | 4708 KB | Output is correct |
5 | Correct | 43 ms | 4708 KB | Output is correct |
6 | Correct | 79 ms | 4840 KB | Output is correct |
7 | Correct | 56 ms | 4708 KB | Output is correct |
8 | Correct | 52 ms | 4708 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 117 ms | 160016 KB | Output is correct |
2 | Correct | 244 ms | 15176 KB | Output is correct |
3 | Correct | 223 ms | 54964 KB | Output is correct |
4 | Correct | 197 ms | 30516 KB | Output is correct |
5 | Correct | 470 ms | 13176 KB | Output is correct |
6 | Correct | 714 ms | 4964 KB | Output is correct |
7 | Correct | 167 ms | 13364 KB | Output is correct |
8 | Correct | 192 ms | 21812 KB | Output is correct |