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

input :

• t (1 ≤ t ≤ 500)
• n l r s (1 ≤ n ≤ 500)(1 ≤ l ≤ r ≤ n)(1 ≤ s ≤ n(n+1) / 2).

output :

• n integers — a permutation of length n that fits the condition above if such a permutation exists;
  -1, otherwise.
  조건을 만족하는 경우 이에 해당하는 순열을 출력하시오. 그렇지 않은 경우에는 -1을 출력하시오.

조건 :

• s = pl + pl+1 + … + pr .

• A permutation is a sequence of n integers from 1 to n

---

결국 l ~ r번째에 존재하는 원소의 합이 s가 될 수 있는지를 묻는 것이다.

범위

l ~ r번째의 원소의 개수는 몇 개 일까? r - l + 1개이다.
그러면 이 개수만큼 수를 넣을 떄 얻을 수 있는 최소와 최대값이 존재한다.
우리 입력받은 s는 이 사이에 존재해야 한다. 그렇지 않은 경우에는 -1을 출력한다.

구현

우리는 동일한 수를 넣을 수는 없다. 그래서 limit을 설정한 후에 이 모든 숫자를 합했을 때 s가 되는 값을 찾으면 멈추게 하는 것이다.

마지막에는 원하는 인덱스에 이 값을 넣어야 하기 때문에 인덱스를 기준으로 현재 값이 l ~ r이라면 계산해둔 배열을 그렇지 않은 경우에는 num값을 넣어준다.

import sys

for _ in range(int(sys.stdin.readline())):
    n, l, r, s = map(int, sys.stdin.readline().split())
    k = r - l + 1

    low_sum, high_sum = sum(range(1, k + 1)), sum(range(n - k + 1, n + 1))
    if s < low_sum or high_sum < s:
        print(-1)
        continue

    idx, limit = k, n
    temp = [i for i in range(k + 1)]
    while sum(temp) != s:
        temp[idx] += 1

        if temp[idx] == limit:
            idx -= 1
            limit -= 1

    ans, idx, num = [], 1, 1
    for i in range(1, n + 1):
        if l <= i <= r:
            ans.append(temp[idx])
            idx += 1
            continue

        while num in temp:
            num += 1
        ans.append(num)
        num += 1


    print(*ans)