QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#142135 | #6693. Fast and Fat | LINTONG | WA | 120ms | 3496kb | C++14 | 1.2kb | 2023-08-18 15:31:11 | 2023-08-18 15:31:13 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<3)+(s<<1)+ch-'0';
ch=getchar();
}
return s*w;
}
int t,n,ans;
struct tree{
int v,w;
}tr[1000005];
bool cmp(tree a,tree b){
if(a.v!=b.v)return a.v<b.v;
return a.w<b.w;
}
bool check(int x){
priority_queue<int>q1,q2;
for(int i=1;i<=n;i++){
if(tr[i].v>=x)q1.push(tr[i].v+tr[i].w-x);
else q2.push(tr[i].w);
}
if(q1.size()<q2.size())return 0;
for(int i=1;i<=q2.size();i++){
int x=q1.top(),y=q2.top();
q1.pop();q2.pop();
if(x<y)return 0;
}
return 1;
}
signed main(){
t=read();
while(t--){
n=read();
ans=1;
for(int i=1;i<=n;i++){
tr[i].v=read(),tr[i].w=read();
}
sort(tr+1,tr+n+1,cmp);
int l=1,r=2000000000;
while(l<=r){
int mid=l+r>>1;
if(check(mid))ans=mid,l=mid+1;
else r=mid-1;
}
cout<<ans<<endl;
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3496kb
input:
2 5 10 5 1 102 10 100 7 4 9 50 2 1 100 10 1
output:
8 1
result:
ok 2 number(s): "8 1"
Test #2:
score: -100
Wrong Answer
time: 120ms
memory: 3452kb
input:
10000 4 280251502 664541723 375808746 641141991 95134537 898607509 455259328 944978891 2 798417052 547329847 785434740 991778535 6 623628702 857611223 275667427 453747403 292209526 283132767 330752033 988721243 470297536 608192332 477186035 325224271 3 280572174 994054447 306566740 923535026 3781360...
output:
375808746 785434740 470297536 280572174 704877362 960871619 691253609 560579095 136979645 399988835 610497257 576427565 636500913 315900406 370430730 526259135 781258283 631916852 300930080 419999540 667381564 479323438 530080165 391912906 708925499 467782812 457987604 389750718 447390353 696516804 ...
result:
wrong answer 1st numbers differ - expected: '352409014', found: '375808746'