QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#224878 | #7617. Spectacle | mendicillin2# | WA | 61ms | 12592kb | C++17 | 1.1kb | 2023-10-23 16:30:02 | 2023-10-23 16:30:03 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
const int N=2e5+5;
int a[N];
struct node{
int pos,val;
};
inline bool operator < (node x,node y)
{
return x.val>y.val;
}
priority_queue<node> q;
int lef[N],rig[N];
bool vis[N];
signed main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
for(int i=1;i<=n;i++) a[i]=a[i+1]-a[i];
for(int i=1;i<=n-1;i++) q.push((node){i,a[i]});
for(int i=1;i<=n-1;i++)
{
if(i>1) lef[i]=i-1;
if(i<n-1) rig[i]=i+1;
}
int ans=0;
vis[0]=true;
for(int i=1;i<=n/2;i++)
{
while(true)
{
node now=q.top(); q.pop();
int p=now.pos, k1=lef[p], k2=rig[p];
//if(i==2) cout<<p<<" "<<k1<<" "<<k2<<" "<<"yes"<<endl;
if(!vis[p])
{
//cout<<p<<" "<<k1<<" "<<k2<<" "<<"yes"<<endl;
vis[k1]=vis[k2]=true;
ans=max(ans,now.val);
rig[lef[k1]]=rig[k2];
lef[rig[k2]]=lef[k1];
lef[p]=lef[k1];
rig[p]=rig[k2];
a[p]=max(a[k2],a[k1]);
q.push((node){p,a[p]});
cout<<ans<<" ";
break;
}
}
}
cout<<"\n";
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5512kb
input:
6 100 13 20 14 10 105
output:
1 5 6
result:
ok single line: '1 5 6 '
Test #2:
score: 0
Accepted
time: 1ms
memory: 5440kb
input:
2 1 1000000000000000000
output:
999999999999999999
result:
ok single line: '999999999999999999 '
Test #3:
score: -100
Wrong Answer
time: 61ms
memory: 12592kb
input:
200000 30977570544127554 30977570529630987 30977570554040634 30977570903666181 30977570284338326 30977570675313216 30977569987827221 30977570780807305 30977570623822067 30977570207823010 30977569932624714 30977570440962037 30977570343703869 30977570239637322 30977570141845422 30977570372368100 30977...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 ...
result:
wrong answer 1st lines differ - expected: '0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...99 9999 10000 10000 10000 10000', found: '0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... 7775 7775 7775 7775 7775 7775 '