oj.uz

Submission #708395

# Submission time Handle Problem Language Result Execution time Memory
708395 2023-03-11T16:33:28 Z auslander Table Tennis (info1cup20_tabletennis) C++17
72 / 100
 3000 ms 222304 KB 
#include <iostream>
#include <map>
#include <iterator>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
typedef long long ll;

const int N = 200005;
ll arr[N];
map<ll, ll>mp;
map<ll, pair<vector<ll>, ll>>r;
int main()
{
	ll i, j, n, k;
	cin >> n >> k;
	for (i = 0; i < n + k; i++)
	{
		cin >> arr[i];
		mp[arr[i]]++;
	}
	sort(arr, arr + k);
	for (i = 0; i <= k; i++)
	{
		for (j = n + k - 1; j - i + 1 >= n; j--)
		{
			ll w = arr[i] + arr[j];
			ll q = 1 * (j - i + 1);
			set<ll>st;
			for (int e = i; e <= j; e++)
			{
				int sz = st.size();
				st.insert(arr[e]);
				st.insert(w - arr[e]);
				ll qq = 2;
				if (w - arr[e] == arr[e])
					qq = 1;
				if (st.size() - sz == qq)
				{
					q -= abs(mp[arr[e]] - mp[w - arr[e]]);
				}
			}
			if (q < n)
			{
				mp[arr[j]]--;
				continue;
			}
			st.erase(st.begin(), st.end());
			ll y = n / 2;
			multiset<ll> res;
			for (int e = i; e <= j && y > 0; e++)
			{
				if (mp[arr[e]] && mp[w - arr[e]])
				{
					if (mp[arr[e]] == 1 && arr[e] == w - arr[e])
					{

					}
					else
					{
						res.insert(arr[e]);
						res.insert(w - arr[e]);
						mp[arr[e]]--;
						mp[w - arr[e]]--;
						y--;
					}
				}
			}
			//cout << i << ' ' << j << endl;
			for (multiset<ll>::iterator it = res.begin(); it != res.end(); it++)
			{
				cout << *it << ' ';
			}
			return 0;
		}
		for (j = n + k - 1; j - i + 1 >= n; j--)
		{
			mp[arr[j]]++;
		}
		mp[arr[i]]--;
	}

	return 0;
}

Compilation message

tabletennis.cpp: In function 'int main()':
tabletennis.cpp:39:24: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   39 |     if (st.size() - sz == qq)
      |         ~~~~~~~~~~~~~~~^~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2760 KB Output is correct
2 Correct 470 ms 47516 KB Output is correct
3 Correct 398 ms 37140 KB Output is correct
4 Correct 405 ms 37244 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 756 ms 67504 KB Output is correct
2 Correct 498 ms 47444 KB Output is correct
3 Correct 858 ms 77624 KB Output is correct
4 Correct 497 ms 49016 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 852 KB Output is correct
2 Correct 342 ms 18124 KB Output is correct
3 Correct 7 ms 1236 KB Output is correct
4 Correct 260 ms 26108 KB Output is correct
5 Correct 9 ms 1236 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 212 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 340 KB Output is correct
2 Correct 178 ms 14452 KB Output is correct
3 Correct 22 ms 3228 KB Output is correct
4 Correct 154 ms 18620 KB Output is correct
5 Correct 20 ms 3308 KB Output is correct
6 Correct 71 ms 1740 KB Output is correct

Subtask #7
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Execution timed out 3054 ms 217180 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 6076 KB Output is correct
2 Execution timed out 3077 ms 222304 KB Time limit exceeded
3 Halted 0 ms 0 KB -