Problem:


Score : 2000 points

Problem Statement

You are given a permutation P_1 ... P_N of the set {1, 2, ..., N}.

You can apply the following operation to this permutation, any number of times (possibly zero):

Choose two indices i,j (1 ≦ i < j ≦ N), such that j - i ≧ K and |P_i - P_j| = 1.
Then, swap the values of P_i and P_j.

Among all permutations that can be obtained by applying this operation to the given permutation, find the lexicographically smallest one.

Constraints

2≦N≦500,000

1≦K≦N-1

P is a permutation of the set {1, 2, ..., N}.

Input

The input is given from Standard Input in the following format:

N K
P_1 P_2 ... P_N

Output

Print the lexicographically smallest permutation that can be obtained.

Sample Input 1

4 2
4 2 3 1

Sample Output 1

2
1
4
3

One possible way to obtain the lexicographically smallest permutation is shown below:

4 2 3 1

4 1 3 2

3 1 4 2

2 1 4 3

Sample Input 2

5 1
5 4 3 2 1

Sample Output 2

1
2
3
4
5

Sample Input 3

8 3
4 5 7 8 3 1 2 6

Sample Output 3

1
2
6
7
5
3
4
8



Sample input:
4 2
4 2 3 1


Sample output:
2
1
4
3

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
nums = list(map(int, input().split()))
dict_indexs = {}
for i, num in enumerate(nums):
    dict_indexs[num - 1] = i
while True:
    flag = False
    for i in range(n - 1):
        a = dict_indexs[i]
        b = dict_indexs[i + 1]
        if a - b >= k:
            dict_indexs[i] = b
            dict_indexs[i + 1] = a
            flag = True
    if flag:
        continue
    else:
        break
for i in range(n):
    print(dict_indexs[i]+1)

Submission status: Wrong Answer

Solution code:
NK=input()
NK="".join(NK).rstrip("\n").split(" ")
N,K,ans=int(NK[0]),int(NK[1]),[]
DP=[0 for s in range(N+1)]#各数字があるかどうか[数字],取りだせるのがindex
lis=input()
lis = "".join(lis).split(" ")
lis=[int(s) for s in lis]
print(lis)
St=0
for s in range(N):
	DP[lis[s]]=s+1
	#if DP[lis[s]]!=0:
		#DP[lis[s]]+=[s+1]#同じ数字が複数個ある場合の処理
def search(num):
	#if DP[num] 複数ある場合の処理
	comp=DP[num]#先頭が4の場合はここで3を探す
	if comp<DP[num+1]:
		return 0
	return comp#なかった場合は初期値の0を返す

def sort(START):
	global St
	compare=START #この場合はlis[0]がSTART?
	comp=search(compare-1)
	start=DP[START]
	if (comp==0): #& (start==1):
		#DP[lis[0]]=0
		#ans.append(lis.pop(0))#先頭がこれ以上小さくなることはないので取り出す
		#for s in range(len(DP)):
			#if DP[s]==0:
				#continue
			#DP[s]-=1
		St+=1
		return
	#print(str(comp)+" "+str(start))
	if (comp-start)<K:
		#print("<K")
		sort(lis[comp-1])
		return
	if (comp-start)>=K :
		#print(">=K")
		temp=DP[lis[start-1]]
		DP[lis[start-1]]=comp
		DP[lis[comp-1]]=temp
		temp=lis[start-1]
		lis[start-1]=lis[comp-1]
		lis[comp-1]=temp
#elif compが複数だった場合の処理
#elif 存在するが距離がK以下の場合の処理　そこからK以上のものだけを探せばいい。証明済み
d=0

while St!=N-1:
	sort(lis[St])
	#print(DP)
	print(lis)
	#print(ans)
	#d+=1
	#if d==20:
		#break

#print(ans)
for s in range(len(lis)):
	print(lis[s])

Submission status: Wrong Answer

Solution code:
NK=input()
NK="".join(NK).rstrip("\n").split(" ")
N,K,ans=int(NK[0]),int(NK[1]),[]
DP=[0 for s in range(N+1)]#各数字があるかどうか[数字],取りだせるのがindex
lis=input()
lis = "".join(lis).split(" ")
lis=[int(s) for s in lis]
print(lis)
St=0
for s in range(N):
	DP[lis[s]]=s+1
def search(num):
	comp=DP[num]#先頭が4の場合はここで3を探す
	if comp<DP[num+1]:
		return 0
	return comp#なかった場合は初期値の0を返す

def sort(START):
	global St
	compare=START #この場合はlis[0]がSTART?
	comp=search(compare-1)
	start=DP[START]
	if (comp==0): #& (start==1):
		St+=1
		return
	if (comp-start)<K:
		sort(lis[comp-1])
		return
	if (comp-start)>=K :
		temp=DP[lis[start-1]]
		DP[lis[start-1]]=comp
		DP[lis[comp-1]]=temp
		temp=lis[start-1]
		lis[start-1]=lis[comp-1]
		lis[comp-1]=temp
while St!=N-1:
	sort(lis[St])
for s in range(len(lis)):
	print(lis[s])

Submission status: Wrong Answer

Solution code:



NK=input()
NK="".join(NK).rstrip("\n").split(" ")
N,K,ans=int(NK[0]),int(NK[1]),[]
DP=[0 for s in range(N+1)]#各数字があるかどうか[数字],取りだせるのがindex
lis=input()
lis = "".join(lis).split(" ")
lis=[int(s) for s in lis]
for s in range(N):
	DP[lis[s]]=s+1
def search(num):
	comp=DP[num]#先頭が4の場合はここで3を探す
	if comp<DP[num+1]:
		return 0
	return comp#なかった場合は初期値の0を返す

def sort(START):
	compare=START #この場合はlis[0]がSTART?
	comp=search(compare-1)
	start=DP[START]
	if (comp==0): #& (start==1):
		DP[lis[0]]=0
		ans.append(lis.pop(0))#先頭がこれ以上小さくなることはないので取り出す
		for s in range(len(DP)):
			if DP[s]==0:
				continue
			DP[s]-=1
		return
	if (comp-start)<K:
		sort(lis[comp-1])
		return
	if (comp-start)>=K :
		temp=DP[lis[start-1]]
		DP[lis[start-1]]=comp
		DP[lis[comp-1]]=temp
		temp=lis[start-1]
		lis[start-1]=lis[comp-1]
		lis[comp-1]=temp
while lis:
	sort(lis[0])
for s in range(len(ans)):
	print(ans[s])

Submission status: Wrong Answer

Solution code:
NK=input()
NK="".join(NK).rstrip("\n").split(" ")
N,K,ans=int(NK[0]),int(NK[1]),[]
DP=[0 for s in range(N+1)]#各数字があるかどうか[数字],取りだせるのがindex
lis=input()
lis = "".join(lis).split(" ")
lis=[int(s) for s in lis]
for s in range(N):
	DP[lis[s]]=s+1
def search(num):
	comp=DP[num]#先頭が4の場合はここで3を探す
	if comp<DP[num+1]:
		return 0
	return comp#なかった場合は初期値の0を返す

def sort(START):
	compare=START #この場合はlis[0]がSTART?
	comp=search(compare-1)
	start=DP[START]
	if (comp==0): #& (start==1):
		DP[lis[0]]=0
		ans.append(lis.pop(0))#先頭がこれ以上小さくなることはないので取り出す
		for s in range(len(DP)):
			if DP[s]==0:
				continue
			DP[s]-=1
		return
	if (comp-start)<K:
		sort(lis[comp-1])
		return
	if (comp-start)>=K :
		temp=DP[lis[start-1]]
		DP[lis[start-1]]=comp
		DP[lis[comp-1]]=temp
		temp=lis[start-1]
		lis[start-1]=lis[comp-1]
		lis[comp-1]=temp
while lis:
	sort(lis[0])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = input().split()
N,K = int(N), int(K)
P = [[int(x),i] for i,x in enumerate(input().split())]
P = sorted(P)
# [(1, 3), (2, 1), (3, 2), (4, 0)]
flag = False
i = -1
while(True):

    if P[i-1][1] - P[i][1] >= K:
        temp = P[i-1][1]
        P[i-1][1] = P[i][1]
        P[i][1] = temp
        flag = True
        
    elif i == -(len(P)-1):
        if flag == False:
            break
        i = -1
        flag = False

    else:
        i=i-1
        

       
#print(answer)
for i in sorted(P, key = lambda p:p[1]):
    print(i[0])

Submission status: Time Limit Exceeded

Solution code:
N, K = [int(x) for x in input().split()]
nums = {int(x):i for i, x in enumerate(input().split())}
swap = True
while swap:
  swap = False
  for x in range(1, N):
    if nums[x] - nums[x+1] >= K:
      nums[x], nums[x+1] = nums[x+1], nums[x]
      swap = True
   

for k, v in sorted(nums.items(), key=lambda item: item[1]):
  print(k)

Submission status: Time Limit Exceeded

Solution code:
N, K = [int(x) for x in input().split()]
nums = [int(x) for x in input().split()]

def f_swap(nums, N, K):
  for i in range(0, N-K):
    for j in range(i+K, N):
      if nums[i] - nums[j] == 1:
        nums[i], nums[j] = nums[j], nums[i]
        return 1
  return 0

while True:
  if not f_swap(nums, N, K):
    break

for n in nums:
  print(n)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def func():
    line1 = input('')
    line2 = input('')
    line1 = line1.split(' ')
    line2 = line2.split(' ')

    N = int(line1[0])
    K = int(line1[1])
    
    ar = np.zeros([N],np.int)
    for i in range(0,N):
        ar[i] = line2[i]
    flag = True
    while flag:
        flag = False
        for i in range(0,N):
            for j in range(i+K,N):
                if(np.abs(ar[i] - ar[j]) == 1):
                    if(ar[i] > ar[j]):
                        tmp = ar[i]
                        ar[i] = ar[j]
                        ar[j] = tmp
                        flag = True

    for i in range(0,N):
        print(ar[i])

func()

Submission status: Time Limit Exceeded

Solution code:
input_word = input()
input_list = input_word.split(" ")
N = int(input_list[0])
K = int(input_list[1])
input_word = input()
tmp_list = input_word.split(" ")
input_list = [ int(i) for i in tmp_list ]

while True:
  flag = 0
  for i in range(1,N):
    number = input_list.index(i)
    number_1 = input_list.index(i+1)
    if number - number_1 >= K:
        input_list[number_1],input_list[number] = input_list[number],input_list[number_1]
        flag = 1
        break
  if flag == 0:
    break

for i in input_list:
  print(i)

Submission status: Time Limit Exceeded

Solution code:
input_word = input()
input_list = input_word.split(" ")
N = int(input_list[0])
K = int(input_list[1])
input_word = input()
tmp_list = input_word.split(" ")
input_list = [ int(i) for i in tmp_list ]

while True:
  flag = 0
  for i in range(1,N+1):
    number = input_list.index(i)
    for j in range(0,number):
      if number - j >= K:
        if input_list[j] - i == 1:
          input_list[j],input_list[number] = input_list[number],input_list[j]
          flag = 1
          break
    if flag == 1:
      break
  if flag == 0:
    break

for i in input_list:
  print(i)

Submission status: Time Limit Exceeded

Solution code:
n, k = (int(s) for s in input().strip().split(' '))
p = [int(s) for s in input().strip().split(' ')]
index = len(p)
while index > k:
    changed = False
    for i in range(0, index - k):
        if p[i] == p[index - 1] + 1:
            p[i], p[index - 1] = p[index - 1], p[i]
            changed = True
            index = len(p)
            break
    if not changed:
        index -= 1
[print(str(a)) for a in p]

Submission status: Time Limit Exceeded

Solution code:
n, k = (int(s) for s in input().strip().split(' '))
p = [int(s) for s in input().strip().split(' ')]
index = len(p)
while index > 0:
    changed = False
    for i in range(0, index - k):
        if p[i] == p[index - 1] + 1:
            p[i], p[index - 1] = p[index - 1], p[i]
            changed = True
            index = len(p)
            break
    if not changed:
        index -= 1
[print(str(a)) for a in p]

Submission status: Accepted

Solution code:
def invert(p, q):
    for i, pi in enumerate(p): q[pi] = i

def sort_insertion(k, data, first, last):
    length = last - first
    if length <= 2:
        if length == 2 and data[first] - data[first + 1] >= k:
            data[first], data[first + 1] = data[first + 1], data[first]
        return
    for i in range(first + 1, last):
        v = data[i]
        for t in range(i - 1, first - 1, -1):
            if data[t] - v < k:
                t += 1
                break
        data[t + 1:i + 1] = data[t:i]
        data[t] = v

def sort_merge(k, data, first, last):
    if last - first < 10:
        sort_insertion(k, data, first, last)
        return

    middle = (first + last) // 2
    sort_merge(k, data, first, middle)
    sort_merge(k, data, middle, last)
    bounds = data[first:middle]
    for i in range(len(bounds) - 2, -1, -1):
        bounds[i] = min(bounds[i + 1], bounds[i])
    tmp = data[first:middle]

    first_len = middle - first
    head1 = 0
    head2 = middle
    for ohead in range(first, last):
        if head1 == first_len or head2 == last:
            data[ohead:ohead + first_len - head1] = tmp[head1:first_len]
            return
        elif bounds[head1] - data[head2] >= k:
            data[ohead] = data[head2]
            head2 += 1
        else:
            data[ohead] = tmp[head1]
            head1 += 1

n, k = (int(s) for s in input().split(' '))
p = [int(s) - 1 for s in input().split(' ')]

q = list(p)
invert(p, q)
sort_merge(k, q, 0, n)
invert(q, p)

for pi in p: print(pi + 1)