QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#624182 | #7617. Spectacle | LX1288# | RE | 0ms | 0kb | C++20 | 828b | 2024-10-09 15:10:12 | 2024-10-09 15:10:13 |
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
int const N=2e6+3;
int n,r[N],fa[N],sz[N],ans[N];
struct node{
int x,I,J;
}a[N];
bool cmp(node A,node B){
return A.x<B.x;
}
int find(int x){
if (x==fa[x]) return fa[x];
else fa[x]=find(fa[x]);
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0);
cin>>n;
for (int i=1;i<=n;i++) cin>>r[i];
sort(r+1,r+n+1);
for (int i=1;i<n;i++)
a[i].x=r[i+1]-r[i],a[i].I=i,a[i].J=i+1;
sort(a+1,a+n,cmp);
for (int i=1;i<=n;i++) fa[i]=i,sz[i]=1;
int cnt=0;
for (int i=1;i<n;i++){
int X=a[i].I,Y=a[i].J;
X=find(X),Y=find(Y);
// cout<<X<<' '<<Y<<endl;
if (X==Y) continue;
if (sz[X]%2==1 && sz[Y]%2==1) ans[++cnt]=a[i].x;
fa[X]=Y;
sz[Y]+=sz[X];
}
for (int i=1;i<=(n/2);i++) cout<<ans[i]<<' ';
return 0;
}
详细
Test #1:
score: 0
Runtime Error
input:
6 100 13 20 14 10 105