Submission #3301282


Source Code Expand

Copy
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<bitset>
#include<stack>
#include<cassert>
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define mem(x,y) memset(x,y,sizeof x)
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
const int INF=2e9;
const db eps=1e-12;
template<typename T>
inline void read(T &x) {
	x=0; int f=1; char ch=getchar();
	while( (ch<'0' || ch>'9') && ch!='-') ch=getchar(); if(ch=='-') {f=-1; ch=getchar();}
	while(ch>='0' && ch <='9') x=x*10+ch-'0',ch=getchar();
	x*=f;
}
//==========================head template==========================
const int N=100010;
ll d[N];
int n;
map<ll,int> key;
pli seq[N];
int fa[N],sz[N];
ll ret[N];
signed main() {
  read(n);
  for(int i=1;i<=n;i++) read(d[i]);
  for(int i=1;i<=n;i++) key[d[i]]=i;
  for(int i=1;i<=n;i++) seq[i]=mp(d[i],i);
  sort(seq+1,seq+n+1); reverse(seq+1,seq+n+1);
  for(int i=1;i<=n;i++) sz[i]=1;
  for(int i=1;i<n;i++) {
    int u=seq[i].S;
    ll delta=d[u]+sz[u]-(n-sz[u]);
    //printf("%lld %d\n",delta,u);
    if(!key.count(delta)) {puts("-1"); return 0;}
    fa[u]=key[delta];
    sz[fa[u]]+=sz[u];
    ret[fa[u]]+=ret[u]+sz[u];
  }
  if(seq[n].F!=ret[seq[n].S]) {
    puts("-1"); return 0;
  }
  for(int i=1;i<=n;i++)
    if(fa[i]) {printf("%d %d\n",i,fa[i]);}
  return 0;
}

Submission Info

Submission Time
Task F - Distance Sums
User functionendless
Language C++14 (GCC 5.4.1)
Score 900
Code Size 1621 Byte
Status
Exec Time 82 ms
Memory 11520 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample1.txt, sample2.txt, sample3.txt
All 900 / 900 sample1.txt, sample2.txt, sample3.txt, 1.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 2.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 3.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 4.txt, 40.txt, 41.txt, 42.txt, 5.txt, 6.txt, 7.txt, 8.txt, 9.txt, sample1.txt, sample2.txt, sample3.txt
Case Name Status Exec Time Memory
1.txt 2 ms 384 KB
10.txt 81 ms 11520 KB
11.txt 59 ms 10368 KB
12.txt 53 ms 10368 KB
13.txt 63 ms 10368 KB
14.txt 82 ms 11520 KB
15.txt 80 ms 11520 KB
16.txt 81 ms 11520 KB
17.txt 80 ms 11520 KB
18.txt 54 ms 10368 KB
19.txt 81 ms 11520 KB
2.txt 2 ms 384 KB
20.txt 81 ms 11520 KB
21.txt 46 ms 9216 KB
22.txt 81 ms 11520 KB
23.txt 80 ms 11520 KB
24.txt 72 ms 10496 KB
25.txt 52 ms 10368 KB
26.txt 52 ms 9984 KB
27.txt 52 ms 10368 KB
28.txt 50 ms 10368 KB
29.txt 81 ms 11520 KB
3.txt 7 ms 1408 KB
30.txt 81 ms 11520 KB
31.txt 80 ms 11520 KB
32.txt 81 ms 11520 KB
33.txt 67 ms 10368 KB
34.txt 80 ms 11520 KB
35.txt 67 ms 10368 KB
36.txt 67 ms 10368 KB
37.txt 81 ms 11520 KB
38.txt 80 ms 11520 KB
39.txt 80 ms 11520 KB
4.txt 5 ms 1280 KB
40.txt 81 ms 11520 KB
41.txt 82 ms 11520 KB
42.txt 64 ms 9344 KB
5.txt 38 ms 5888 KB
6.txt 80 ms 11520 KB
7.txt 80 ms 11520 KB
8.txt 80 ms 11520 KB
9.txt 81 ms 11520 KB
sample1.txt 1 ms 256 KB
sample2.txt 1 ms 256 KB
sample3.txt 1 ms 256 KB