D. Corrupted Array | Round #713 Div.3

LONGNEW·2021년 7월 26일
0

CP

목록 보기
65/155

https://codeforces.com/contest/1512/problem/D
시간 2초, 메모리 256MB

input :

  • t (1 ≤ t ≤ 104)
  • n (1 ≤ n ≤ 2 * 105)
  • b1, b2, …, bn + 2 (1 ≤ bi ≤ 109)

output :

  • "-1", if the array b could not be obtained from any array a;
    n integers b1, b2, …, bn + 2, otherwise.
    b에서 배열 a를 얻을 수 없다면 "-1"을 그렇지 않다면 배열 a를 출력하시오.

조건 :

  • some array a1, a2, …, an + 2 was guessed;
    a 배열이 존재합니다.

  • array a was written to array b, i.e. bi=ai (1≤i≤n);
    a 배열을 b 배열에다가 작성했습니다.

  • The (n+1)-th element of the array b is the sum of the numbers in the array a, i.e. bn + 2 = a1, a2, …, an;
    b의 n + 1번째 원소는 a 배열의 합입니다.

  • The (n+2)-th element of the array b was written some number x (1≤x≤109), i.e. bn+2=x; The
    b의 n + 2번째 원소는 임의의 x입니다.

  • array b was shuffled.
    b배열은 섞여졌습니다.


우리가 입력받은 값을 모두 더하는 경우 이 값은 2A + x가 됩니다. A는 배열 a의 합을 의미한다.
왜냐하면 b의 가장 큰 값? 혹은 두번째로 큰 값이 a 배열의 합이기에 두 번 더한 것으로 볼 수 있다.

가장 큰 값을 합으로 보거나 두 번째를 합으로 볼 수 있다.
결국 a 배열 원소 모두를 합한 값이 b의 n + 1번째 값이니까 이 값이 매우 클것이라는 것을 알 수 있다. 그렇기에 두 가지 경우가 존재한다.
정렬 했을 때 가장 뒤에 존재하는 값이 합이다.
또는 두 번째 값이다.

x

그래서 -1에 존재하는 가장 큰 값이 합을 나타낸다고 할 때 이 값의 2배를 뺀 값을 우리는 x로 볼 수 있다. 그리고 이 x를 제거해버리면 우리는 a를 얻을 수 있다.

근데 그렇지 않은 경우에는?
두 번째 값을 합으로 보기 때문에 그 앞에 존재하는 모든 값을 더한 값과 동일해야 한다.

이 두 가지를 모두 만족하지 않는 경우에는 -1을 출력하자.

import sys
t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    data = list(map(int, sys.stdin.readline().split()))
    data.sort()

    x = sum(data) - data[-1] * 2
    if x in data[:len(data) - 1]:
        data.remove(x)
        print(*data[:n])
    else:
        if sum(data[:n]) == data[n]:
            print(*data[:n])
        else:
            print(-1)

0개의 댓글