Submission #68586130

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
struct node{
	int id,d;
}a[100005];
map<int,int> pos;
bool cmp(node x,node y){
	return x.d>y.d;
}
vector<int> V[100005];
int f[100005],sz[100005];
int fd(int x){
	if(x==f[x]) return x;
	return f[x]=fd(f[x]);
}
void link(int u,int v){
	V[u].push_back(v);
	V[v].push_back(u);
	u=fd(u),v=fd(v);
	if(u==v) return;
	f[u]=v;
	sz[v]+=sz[u];
}
void dfs(int u,int fa){
	sz[u]=sz[fa]+1;
	for(int v:V[u]){
		if(v==fa) continue;
		dfs(v,u);
	} 
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		int d;cin>>d;
		a[i]={i,d};
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++){
		f[i]=i,sz[i]=1;
		pos[a[i].d]=i;
	}
	for(int i=1;i<n;i++){
		int dy=a[i].d;
		int s=sz[fd(a[i].id)];
		int dx=dy-n+2*s;
		if(!pos.count(dx)||pos[dx]<=i){
			cout<<-1<<"\n";
			return 0;
		}
//		cout<<a[i].id<<' '<<a[pos[dx]].id<<"\n";
		link(a[i].id,a[pos[dx]].id);
	}
	dfs(a[n].id,0);
	int t=0;
	for(int i=1;i<=n;i++) t+=sz[i];
	if(t-n!=a[n].d){
		cout<<-1<<"\n";
		return 0;
	}
	for(int i=1;i<=n;i++){
		for(int j:V[i]){
			if(j>i) cout<<i<<" "<<j<<"\n";
		}
	}
}

Submission Info

Judge Result