Submission #18941962

---

Source Code Expand

/*
after dusk passed,
there is a starry sky.
*/
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define m_k make_pair
#define int long long
using namespace std;
const int N=1e5+100;
int n,sz[N],d[N],de[N];
unordered_map <int,int> mp;
vector <pair<int,int> > ans;
vector <int> e[N];
bool bl;
struct node
{
	int d,id;
}sh[N];
bool cmp(node a,node b){return a.d<b.d;}
inline int read()
{
	int f=1,x=0;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
	return x*f;
}
void dfs(int x)
{
	d[x]=de[x];
	for (int i=0;i<(int)e[x].size();i++)
	{
		int u=e[x][i];
		de[u]=de[x]+1;
		dfs(u);
		d[x]+=d[u];
	}
}
void dfs1(int x)
{
	for (int i=0;i<(int)e[x].size();i++)
	{
		int u=e[x][i];
		d[u]=d[x]-sz[u]+n-sz[u];
		dfs1(u);
	}
}
signed main()
{
	n=read();
	for (int i=1;i<=n;i++) sh[i]=(node){read(),i};
	sort(sh+1,sh+1+n,cmp);
	for (int i=1;i<=n;i++) mp[sh[i].d]=i,sz[i]=1;
	for (int i=n;i>=2;i--)
	{
		int aim=sh[i].d-(n-2ll*sz[i]);
		if (aim>=sh[i].d||!mp.count(aim))
		{
			printf("-1\n");
			return 0;
		}
		sz[mp[aim]]+=sz[i];
		e[mp[aim]].push_back(i);
		ans.push_back(m_k(sh[mp[aim]].id,sh[i].id));
	}
	dfs(1);dfs1(1);
	for (int i=1;i<=n;i++)
	{
		if (sh[i].d!=d[i])
		{
			printf("-1\n");
			return 0;
		}
	}
	for (int i=0;i<(int)ans.size();i++) printf("%lld %lld\n",ans[i].first,ans[i].second);
}

Submission Info

Judge Result