oj.uz

Submission #315748

# Submission time Handle Problem Language Result Execution time Memory
315748 2020-10-23T21:13:05 Z jungsnow Table Tennis (info1cup20_tabletennis) C++14
85 / 100
 408 ms 32412 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 <= 4 * k) {
		for (int i = 1; i < n; ++i) {
			for (int j = i + 1; j <= n; ++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 6 ms 724 KB Output is correct
2 Correct 33 ms 3308 KB Output is correct
3 Correct 34 ms 3188 KB Output is correct
4 Correct 33 ms 3180 KB Output is correct

Subtask #3
14.0 / 14.0

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

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB Unexpected end of file - int32 expected
3 Halted 0 ms 0 KB -

Subtask #5
9.0 / 9.0

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

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 3488 KB Output is correct
3 Correct 33 ms 3308 KB Output is correct
4 Correct 33 ms 3284 KB Output is correct
5 Correct 33 ms 3180 KB Output is correct
6 Correct 33 ms 3308 KB Output is correct
7 Correct 35 ms 3308 KB Output is correct
8 Correct 38 ms 3308 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 408 ms 30840 KB Output is correct
3 Correct 320 ms 32412 KB Output is correct
4 Correct 220 ms 28524 KB Output is correct
5 Correct 122 ms 10144 KB Output is correct
6 Correct 64 ms 3540 KB Output is correct
7 Correct 232 ms 25196 KB Output is correct
8 Correct 211 ms 27420 KB Output is correct