oj.uz

답안 #387552

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
387552 2021-04-09T01:36:07 Z Kevin_Zhang_TW Table Tennis (info1cup20_tabletennis) C++17
100 / 100
 331 ms 33140 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 200005;

int n, k, a[MAX_N], m;

void check(int v) {
	vector<int> ok;

	for (int i = 0, j = m-1;i < j;++i) {
		while (i < j && a[i] + a[j] > v) --j;
		if (i == j) break;
		if (a[i] + a[j] == v) {
			ok.pb(a[i]), ok.pb(a[j]);
			--j;
		}
	}

	if (ok.size() >= n) {
		ok.resize(n);

		sort(AI(ok));

		for (int i = 0;i < n;++i)
			cout << ok[i] << " \n"[i+1==n];

		exit(0);
	}
}
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> k;

	m = n + k;

	for (int i = 0;i < m;++i)
		cin >> a[i];

	int need = k;

	unordered_map<int,int> cnt;

	if (4 * k > m) {
		need = n / 2;
		for (int i = 0;i < m;++i)
			for (int j = i + 1;j < m;++j)
				++cnt[ a[i] + a[j] ];
	}
	else {
		for (int i = 0;i < 2 * k;++i)
			for (int j = 1;j <= 2 * k;++j) {
				++cnt[ a[i] + a[m-j] ];
			}
	}

	for (auto [v, c] : cnt)
		if (c >= need) 
			check(v);
}

Compilation message

tabletennis.cpp: In function 'void check(int)':
tabletennis.cpp:34:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |  if (ok.size() >= n) {
      |      ~~~~~~~~~~^~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 780 KB Output is correct
2 Correct 41 ms 3132 KB Output is correct
3 Correct 42 ms 3044 KB Output is correct
4 Correct 40 ms 3008 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 3072 KB Output is correct
2 Correct 40 ms 3148 KB Output is correct
3 Correct 39 ms 3028 KB Output is correct
4 Correct 39 ms 3000 KB Output is correct

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 2 ms 844 KB Output is correct
3 Correct 3 ms 1100 KB Output is correct
4 Correct 3 ms 1100 KB Output is correct
5 Correct 3 ms 1100 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 204 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 39 ms 3104 KB Output is correct
3 Correct 42 ms 4568 KB Output is correct
4 Correct 58 ms 4552 KB Output is correct
5 Correct 45 ms 4544 KB Output is correct
6 Correct 42 ms 5500 KB Output is correct
7 Correct 42 ms 4580 KB Output is correct
8 Correct 43 ms 4544 KB Output is correct

Subtask #8
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 4200 KB Output is correct
2 Correct 331 ms 30644 KB Output is correct
3 Correct 314 ms 33140 KB Output is correct
4 Correct 298 ms 31076 KB Output is correct
5 Correct 189 ms 12048 KB Output is correct
6 Correct 55 ms 5668 KB Output is correct
7 Correct 174 ms 24104 KB Output is correct
8 Correct 220 ms 25736 KB Output is correct