oj.uz

Submission #315760

# Submission time Handle Problem Language Result Execution time Memory
315760 2020-10-23T21:24:22 Z jungsnow Table Tennis (info1cup20_tabletennis) C++14
100 / 100
 386 ms 32668 KB 
#include<bits/stdc++.h>

using namespace std;

const int N = 155010;

int n, k, a[N];
map<int, int> mp;

bool check(int sum) {
	vector <int> L, R;
	int l = 1, r = n + k, cn = 0;
	while (l < r) {
		if (a[l] + a[r] > sum) {
			if (cn == k) return 0;
			--r;
			++cn;
		} else if (a[l] + a[r] < sum) {
			if (cn == k) return 0;
			++l;
			++cn;
		} else {
			L.push_back(a[l]);
			R.push_back(a[r]);
			++l; --r;
		} 
	}
	for (int x : L) cout<<x<<' ';
	reverse(R.begin(), R.end());
	for (int x : R) cout<<x<<' ';
	return 1;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n + k; ++i) {
		cin >> a[i];
	}		
	if (n <= 3 * k) {
		for (int i = 1; i < n + k; ++i) {
			for (int j = i + 1; j <= n + k; ++j) {
				if (check(a[i] + a[j])) {
					return 0;
				}
			}
		}
	} else {
		for (int i = 1; i <= 2 * k; ++i) {
			for (int j = n - k + 1; j <= n + k; ++j) {
				mp[a[i] + a[j]]++;
			}
		}
		for (auto &ele : mp) {
			if (ele.second >= k) {
				if (check(ele.first)) return 0;
			}
		}
	}
}

Subtask #1
11.0 / 11.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 724 KB Output is correct
2 Correct 32 ms 3308 KB Output is correct
3 Correct 32 ms 3180 KB Output is correct
4 Correct 34 ms 3308 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3308 KB Output is correct
2 Correct 34 ms 3308 KB Output is correct
3 Correct 33 ms 3312 KB Output is correct
4 Correct 38 ms 3180 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #5
9.0 / 9.0

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

Subtask #6
14.0 / 14.0

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

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 35 ms 3224 KB Output is correct
3 Correct 34 ms 3308 KB Output is correct
4 Correct 34 ms 3284 KB Output is correct
5 Correct 33 ms 3308 KB Output is correct
6 Correct 33 ms 3308 KB Output is correct
7 Correct 32 ms 3312 KB Output is correct
8 Correct 32 ms 3308 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 386 ms 30748 KB Output is correct
3 Correct 339 ms 32668 KB Output is correct
4 Correct 233 ms 28652 KB Output is correct
5 Correct 122 ms 10144 KB Output is correct
6 Correct 65 ms 3540 KB Output is correct
7 Correct 215 ms 25328 KB Output is correct
8 Correct 205 ms 27420 KB Output is correct