fork download
copy 
  1. t = int(input())
  2. for _ in range(t):
  3.     n = int(input())
  4.     b = list(map(int, input().split()))
  5.  
  6.     ib = sorted((b[i], i) for i in range(n))
  7.  
  8.     if ib[0][0] != 0:
  9.         print(-1)
  10.         continue
  11.  
  12.     blocks = []
  13.     curr_val = ib[0][0]
  14.     curr_indices = [ib[0][1]]
  15.  
  16.     for i in range(1, n):
  17.         if ib[i][0] == curr_val:
  18.             curr_indices.append(ib[i][1])
  19.         else:
  20.             blocks.append((curr_val, curr_indices))
  21.             curr_val = ib[i][0]
  22.             curr_indices = [ib[i][1]]
  23.     blocks.append((curr_val, curr_indices))
  24.  
  25.     ans_a = [0] * n
  26.     possible = True
  27.     num_blocks = len(blocks)
  28.  
  29.     for i in range(num_blocks - 1):
  30.         diff_b = blocks[i+1][0] - blocks[i][0]
  31.         count_curr = len(blocks[i][1])
  32.  
  33.         if diff_b % count_curr != 0:
  34.             possible = False
  35.             break
  36.  
  37.         val_a = diff_b // count_curr
  38.         if val_a <= 0:
  39.             possible = False
  40.             break
  41.  
  42.         if i > 0 and val_a <= ans_a[blocks[i-1][1][0]]:
  43.             possible = False
  44.             break
  45.  
  46.         for idx in blocks[i][1]:
  47.             ans_a[idx] = val_a
  48.  
  49.     if possible:
  50.         if num_blocks == 1:
  51.             last_val_a = 1
  52.         else:
  53.             last_val_a = ans_a[blocks[-2][1][0]] + 1
  54.  
  55.         for idx in blocks[-1][1]:
  56.             ans_a[idx] = last_val_a
  57.  
  58.     if not possible:
  59.         print(-1)
  60.     else:
  61.         print(*(ans_a))
Success #stdin #stdout 0.07s 14040KB
comments (?)
stdin
copy 
8
1
0
5
0 4 0 4 14
3
4 0 0
3
0 0 0
3
0 1 1
4
1 1 1 1
7
0 4 4 4 4 4 9
5
0 0 0 3 3
stdout
copy 
1
2 5 2 5 6
3 2 2
1 1 1
1 2 2
-1
-1
1 1 1 2 2
https://ideone.com/b34kd0
language:
Python 3 (python  3.12)
created:
2 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!