-
Notifications
You must be signed in to change notification settings - Fork 7
/
reversort_engineering2.py
46 lines (42 loc) · 1.26 KB
/
reversort_engineering2.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# Copyright (c) 2021 kamyu. All rights reserved.
#
# Google Code Jam 2021 Qualification Round - Problem C. Reversort Engineering
# https://codingcompetitions.withgoogle.com/codejam/round/000000000043580a/00000000006d12d7
#
# Time: O(N)
# Space: O(1)
#
def reverse(L, i, j):
while i < j:
L[i], L[j] = L[j], L[i]
i += 1
j -= 1
def reversort_engineering():
N, C = map(int, raw_input().strip().split())
if not (N-1 <= C <= (N+2)*(N-1)//2):
return "IMPOSSIBLE"
result = [0]*N
for i in xrange(N):
l = min(C-(N-1-i)+1, N-i) # greedy
C -= l
if l != N-i:
break
if i%2 == 0:
result[N-1-i//2] = i+1
else:
result[i//2] = i+1
if i%2 == 0:
k = i+1
for j in xrange((N-1-i//2+1)-(N-i), N-1-i//2+1):
result[j] = k
k += 1
reverse(result, (N-1-i//2+1)-(N-i), ((N-1-i//2+1)-(N-i))+l-1) # Space: O(1)
else:
k = i+1
for j in reversed(xrange(i//2, i//2+(N-i))):
result[j] = k
k += 1
reverse(result, (i//2+(N-i)-1)-l+1, i//2+(N-i)-1) # Space: O(1)
return " ".join(map(str, result))
for case in xrange(input()):
print 'Case #%d: %s' % (case+1, reversort_engineering())