#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<ll, ll>
#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define pb push_back
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do( T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do( T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT
const int maxn = 2e5+5;
int a[maxn];
int n, k;
unordered_set<int> tried;
void get(int sum);
bool test(int sum) {
if (tried.count(sum)) return 0;
int lp = 0, rp = n-1;
int imp = 0;
while (lp < rp && imp <= k) {
if (a[lp] + a[rp] == sum) {
++lp; --rp;
}else if (a[lp] + a[rp] < sum) {
++lp; ++imp;
}else{
--rp; ++imp;
}
}
if (imp > k) {
tried.insert(sum);
return 0;
}
get(sum);
return 1;
}
void get(int sum) {
int lp = 0, rp = n-1;
vector<int> ret;
while (lp < rp) {
if (a[lp] + a[rp] == sum) {
ret.pb(lp); ret.pb(rp);
++lp; --rp;
}else if (a[lp] + a[rp] < sum) {
++lp;
}else{
--rp;
}
}
sort(ALL(ret));
for (int t : ret) cout<<a[t]<<' ';
cout<<endl;
exit(0);
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0);
bug(1,2);
cin>>n>>k;
n+=k;
REP(i,n) cin>>a[i];
sort(a, a+n);
if (n <= 200) {
// brute
REP(i,n) {
for (int to = i+1; to <n; ++to) {
// int to = n-i-1-j;
if (i < to && test(a[i] + a[to])) {
// get(a[i] + a[to]);
}
}
}
assert(0);
}
while (1) {
int i = rand() % n;
int j = rand() % (k+1);
int to = n-i-1-j;
if (i < to && test(a[i] + a[to])) {
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3078 ms |
204 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
716 KB |
Output is correct |
2 |
Execution timed out |
3065 ms |
2872 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
3024 KB |
Output is correct |
2 |
Correct |
34 ms |
4508 KB |
Output is correct |
3 |
Execution timed out |
3060 ms |
2380 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
4 ms |
844 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
3 ms |
580 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Execution timed out |
3053 ms |
332 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Execution timed out |
3063 ms |
7492 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
332 KB |
Output is correct |
2 |
Execution timed out |
3076 ms |
82168 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |