ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#211800 | #64. sort | zsy2542068503 | Judgement Failed | / | / | C++11 | 1.5kb | 2024-10-04 11:00:52 | 2024-10-04 11:00:54 |
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;
}
详细
Failed to show details