UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#211799#64. sortzsy2542068503Judgement Failed//C++1.5kb2024-10-04 11:00:112024-10-04 11:00:13

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1e15

inline ll read()
{
	ll x = 0, f = 1;
	char c = getchar();
	while(c < '0' || c > '9')
	{
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9')
	{
		x = (x << 1) + (x << 3) + c - '0';
		c = getchar();
	}
	return x * f;
}

ll n, k;
ll a[100005], b[100005];
ll c[200005];

bool check(ll mid)
{
	ll cnt = 0;
	for(ll i = 1; i <= n; i++)
	{
		cnt += upper_bound(b + 1, b + n + 1, mid - a[i]) - b - 1;
	}
	return cnt >= k;
}

void solve()
{
	sort(a + 1, a + n + 1);
	sort(b + 1, b + n + 1);
	ll l = 0, r = 2e9;
	ll ans = 0;
	while(l <= r)
	{
		ll mid = (l + r) / 2;
		if(check(mid))
		{
			ans = mid;
			r = mid - 1;
		}
		else
		{
			l = mid + 1;
		}
	}
	cout << ans << endl;
}

int main()
{
	n = read();
	ll l = read(), r = read();
	for(ll i = 1; i <= n; i++)
	{
		a[i] = read();
	}
	for(ll i = 1; i <= n; i++)
	{
		b[i] = read();
	}
	if(n < 1000)
	{
		ll tot = 0;
		for(ll i = 1; i <= n; i++)
		{
			for(ll j = 1; j <= n; j++)
			{
				c[++tot] = a[i] + b[j];
			}
		}
		sort(c + 1, c + tot + 1);
		for(ll i = l; i <= r; i++)
		{
			cout << c[i] << " ";
		}
	}
	else if(l == r)
	{
		k = l;
		solve();
	}
	else
	{
		priority_queue<ll> q;
		for(ll i = 1; i <= n; i++)
		{
			for(ll j = 1; j <= n; j++)
			{
				q.push(a[i] + b[j]);
			}
		}
		for(ll i = 1; i < l; i++)
		{
			q.pop();
		}
		for(ll i = l; i <= r; i++)
		{
			cout << q.top() << " ";
		}
	}
	return 0;
}

Details

Failed to show details