oj.uz

Submission #746688

# Submission time Handle Problem Language Result Execution time Memory
746688 2023-05-23T01:04:21 Z Abrar_Al_Samit Table Tennis (info1cup20_tabletennis) C++17
100 / 100
 333 ms 33824 KB 
#include<bits/stdc++.h>
using namespace std;

const int nax = 150402;

int a[nax];
int n, k;

void check(int sum) {
	int l = 1, r = n+k;
	vector<int>b;
	int cur = a[1] + a[n+k];
	while(l<r) {
		if(cur>sum) {
			cur -= a[r];
			--r;
			cur += a[r];
		}
		else if(cur<sum) {
			cur -= a[l];
			++l;
			cur += a[l];
		} else {
			b.push_back(a[l]);
			b.push_back(a[r]);

			if(b.size()==n) {
				sort(b.begin(), b.end());
				for(int x : b) {
					cout<<x<<' ';
				}
				cout<<'\n';
				exit(0);
			}

			++l, --r;
			cur = a[l] + a[r];
		}
	}
}
void PlayGround() {
	cin>>n>>k;
	for(int i=1; i<=n+k; ++i) {
		cin>>a[i];
	}

	if(n+k < 4 * k) {
		for(int i=1; i<=n+k; ++i) {
			for(int j=i+1; j<=n+k; ++j) {
				check(a[i]+a[j]);
			}
		}
	} else {
		map<int, int>cnt;
		for(int i=1; i<=2*k; ++i) {
			for(int j=n-k+1; j<=n+k; ++j) {
				cnt[a[i]+a[j]]++;
			}
		}
		for(auto [x, y] : cnt) {
			if(y >= k) {
				check(x);
			}
		}
	}

	// cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	PlayGround();
	return 0;
}

Compilation message

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

Subtask #1
11.0 / 11.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1024 KB Output is correct
2 Correct 41 ms 4536 KB Output is correct
3 Correct 40 ms 4536 KB Output is correct
4 Correct 36 ms 4456 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 4504 KB Output is correct
2 Correct 37 ms 4508 KB Output is correct
3 Correct 37 ms 4540 KB Output is correct
4 Correct 38 ms 4464 KB Output is correct

Subtask #4
15.0 / 15.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 10 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 36 ms 4636 KB Output is correct
3 Correct 36 ms 4544 KB Output is correct
4 Correct 36 ms 4544 KB Output is correct
5 Correct 36 ms 4572 KB Output is correct
6 Correct 37 ms 5524 KB Output is correct
7 Correct 36 ms 4484 KB Output is correct
8 Correct 33 ms 4540 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 333 ms 32144 KB Output is correct
3 Correct 253 ms 33824 KB Output is correct
4 Correct 180 ms 29840 KB Output is correct
5 Correct 125 ms 11412 KB Output is correct
6 Correct 102 ms 5748 KB Output is correct
7 Correct 195 ms 26408 KB Output is correct
8 Correct 206 ms 28708 KB Output is correct