oj.uz

Submission #387599

# Submission time Handle Problem Language Result Execution time Memory
387599 2021-04-09T03:19:49 Z 8e7 Table Tennis (info1cup20_tabletennis) C++14
100 / 100
 181 ms 3136 KB 
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#define ll long long
#define maxn 160005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
//#include <bits/extc++.h>
//using namespace __gnu_pbds;
//template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//find by order, order of key
int a[maxn];
vector<int> ans;
bool solve(int x, int tot, bool rec, int v, int k) {
	int ret = 0, ind = tot - 1, bad = 0;
	for (int i = 0;i < tot;i++) {
		while (ind >= 0 && a[i] + a[ind] > x) {
			ind--;
		}
		if (ind < i) break;
		if (ind != i && a[i] + a[ind] == x) {
			ret++;
			if (i < ind && rec) ans.push_back(a[i]), ans.push_back(a[ind]);
		} else {
			bad++;
			if (bad > k) return false;
		}
		if (ret == v) {
			return true;
		}
	}
	return false;
}
int main() {
	io
	int n, k;
	cin >> n >> k;
	for (int i = 0;i < n + k;i++) cin >> a[i];
	for (int i = 0;i <= k;i++) {
		for (int j = n + k - 1;j >= n + i - 1;j--) {
			if (i >= j) continue;
			if (solve(a[i] + a[j], n + k, false, n / 2, k)) {
				solve(a[i] + a[j], n + k, true, n / 2, k);
				sort(ans.begin(), ans.end());
				for (int x:ans) cout << x << " ";
				cout << "\n";
				return 0;
			}
		}
	}
}
/*
4 3
1 2 3 4 8 10 20

4 2
1 2 3 4 5 6
 */

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 716 KB Output is correct
2 Correct 40 ms 3040 KB Output is correct
3 Correct 39 ms 3008 KB Output is correct
4 Correct 42 ms 3008 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 3032 KB Output is correct
2 Correct 40 ms 3080 KB Output is correct
3 Correct 42 ms 3136 KB Output is correct
4 Correct 40 ms 3016 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 2 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 440 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 39 ms 3048 KB Output is correct
3 Correct 49 ms 3004 KB Output is correct
4 Correct 40 ms 3036 KB Output is correct
5 Correct 44 ms 3008 KB Output is correct
6 Correct 45 ms 3008 KB Output is correct
7 Correct 41 ms 3076 KB Output is correct
8 Correct 39 ms 3032 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 114 ms 3076 KB Output is correct
3 Correct 40 ms 3064 KB Output is correct
4 Correct 103 ms 3008 KB Output is correct
5 Correct 40 ms 3064 KB Output is correct
6 Correct 181 ms 3064 KB Output is correct
7 Correct 155 ms 3008 KB Output is correct
8 Correct 40 ms 3052 KB Output is correct