Submission #3300261


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];
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];
  }
  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 0
Code Size 1513 Byte
Status
Exec Time 81 ms
Memory 10752 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 900
Status
× 2
× 1
× 43
× 5
Set Name Test Cases
Sample sample1.txt, sample2.txt, sample3.txt
All 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 79 ms 10752 KB
11.txt 59 ms 9600 KB
12.txt 53 ms 9600 KB
13.txt 64 ms 9600 KB
14.txt 80 ms 10752 KB
15.txt 80 ms 10752 KB
16.txt 80 ms 10752 KB
17.txt 80 ms 10752 KB
18.txt 55 ms 9600 KB
19.txt 81 ms 10752 KB
2.txt 2 ms 384 KB
20.txt 80 ms 10752 KB
21.txt 45 ms 8448 KB
22.txt 79 ms 10752 KB
23.txt 80 ms 10752 KB
24.txt 71 ms 9728 KB
25.txt 52 ms 9600 KB
26.txt 52 ms 9216 KB
27.txt 53 ms 9600 KB
28.txt 51 ms 9600 KB
29.txt 80 ms 10752 KB
3.txt 7 ms 1280 KB
30.txt 80 ms 10752 KB
31.txt 79 ms 10752 KB
32.txt 79 ms 10752 KB
33.txt 81 ms 10752 KB
34.txt 80 ms 10752 KB
35.txt 80 ms 10752 KB
36.txt 80 ms 10752 KB
37.txt 80 ms 10752 KB
38.txt 80 ms 10752 KB
39.txt 80 ms 10752 KB
4.txt 5 ms 1152 KB
40.txt 80 ms 10752 KB
41.txt 80 ms 10752 KB
42.txt 63 ms 8704 KB
5.txt 38 ms 5504 KB
6.txt 80 ms 10752 KB
7.txt 80 ms 10752 KB
8.txt 81 ms 10752 KB
9.txt 80 ms 10752 KB
sample1.txt 1 ms 256 KB
sample2.txt 1 ms 256 KB
sample3.txt 1 ms 256 KB