QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#624182#7617. SpectacleLX1288#RE 0ms0kbC++20828b2024-10-09 15:10:122024-10-09 15:10:13

Judging History

你现在查看的是最新测评结果

  • [2024-10-09 15:10:13]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-10-09 15:10:12]
  • 提交

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

output:


result: