提出 #3301282


ソースコード 拡げる

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;
}

提出情報

提出日時
問題 F - Distance Sums
ユーザ functionendless
言語 C++14 (GCC 5.4.1)
得点 900
コード長 1621 Byte
結果
実行時間 82 ms
メモリ 11520 KB

テストケース

セット名 得点 / 配点 テストケース
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
ケース名 結果 実行時間 メモリ
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