oj.uz

Submission #339716

# Submission time Handle Problem Language Result Execution time Memory
339716 2020-12-26T04:47:39 Z wwdd Table Tennis (info1cup20_tabletennis) C++14
100 / 100
 470 ms 44880 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fore(b,c) for(int val0=b;val0<c;val0++)
#define forr(k,c,s) for(int k=c;k<s;k++)
#define pb push_back
#define mmp make_pair
using namespace __gnu_pbds;
using namespace std;
template<typename T>
using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> ii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long double ld;
typedef vector<vii> al;
typedef pair<ll,ll> pl;
typedef vector<ll> vl;
const int INF = 1e9;
const ll INFL = 1LL<<61;
vl fin(const vl& w, ll su, ll n) {
	ll piv = w.size()-1;
	vl ru;
	for(int i=0;i<w.size();i++) {
		while(piv > i && w[i]+w[piv] > su) {
			piv--;
		}
		if(piv <= i) {break;}
		if(ru.size() >= n) {break;}
		if(w[piv] + w[i] == su) {
			ru.push_back(w[piv]);
			ru.push_back(w[i]);
			piv--;
		}
	}
	sort(ru.begin(),ru.end());
	return ru;
}
ll test(const vl& w, ll su) {
	ll piv = w.size()-1;
	ll res = 0;
	for(int i=0;i<w.size();i++) {
		while(piv > i && w[i]+w[piv] > su) {
			piv--;
		}
		if(piv <= i) {break;}
		if(w[piv] + w[i] == su) {res++;
			piv--;
		}
	}
	return res;
}
int main() {
	ios::sync_with_stdio(0);cout.precision(20);cout.tie(0);cin.tie(0);
	ll n,k;
	cin >> n >> k;
	vl w,ord;
	for(int i=0;i<n+k;i++) {
		ll t;
		cin >> t;
		w.push_back(t);
		ord.push_back(i);
	}
	ll res = -1;
	map<ll,ll> bs;
	ll lim = min(ll(w.size()),2*k);
	for(int i=0;i<lim;i++) {
		for(int j=0;j<lim;j++) {
			bs[w[i]+w[w.size()-j-1]]++;
		}
	}
	for(const auto& it: bs) {
		if(it.second >= lim-k) {
			if(test(w,it.first) >= n/2) {
				res = it.first;break;
			}
		}
	}
	vl ans = fin(w,res,n);
	for(int i=0;i<n;i++) {
		if(i > 0) {cout << " ";}
		cout << ans[i];
	}
	cout << '\n';
}

Compilation message

tabletennis.cpp: In function 'vl fin(const vl&, ll, ll)':
tabletennis.cpp:28:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for(int i=0;i<w.size();i++) {
      |              ~^~~~~~~~~
tabletennis.cpp:33:16: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   33 |   if(ru.size() >= n) {break;}
      |      ~~~~~~~~~~^~~~
tabletennis.cpp: In function 'll test(const vl&, ll)':
tabletennis.cpp:46:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for(int i=0;i<w.size();i++) {
      |              ~^~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1256 KB Output is correct
2 Correct 52 ms 5712 KB Output is correct
3 Correct 42 ms 5712 KB Output is correct
4 Correct 43 ms 5712 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 5712 KB Output is correct
2 Correct 43 ms 5712 KB Output is correct
3 Correct 49 ms 5712 KB Output is correct
4 Correct 42 ms 5712 KB Output is correct

Subtask #4
15.0 / 15.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
14.0 / 14.0

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

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 47 ms 5840 KB Output is correct
3 Correct 53 ms 5840 KB Output is correct
4 Correct 46 ms 5840 KB Output is correct
5 Correct 45 ms 5840 KB Output is correct
6 Correct 44 ms 5840 KB Output is correct
7 Correct 46 ms 5840 KB Output is correct
8 Correct 46 ms 5840 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 6124 KB Output is correct
2 Correct 470 ms 42704 KB Output is correct
3 Correct 400 ms 44880 KB Output is correct
4 Correct 262 ms 39632 KB Output is correct
5 Correct 164 ms 15056 KB Output is correct
6 Correct 71 ms 6096 KB Output is correct
7 Correct 289 ms 35152 KB Output is correct
8 Correct 230 ms 38096 KB Output is correct