Problem:


Counting Sort

Counting sort can be used for sorting elements in an array which each of the n input elements is an integer in the range 0 to k. The idea of counting sort is to determine, for each input element x, the number of elements less than x as C[x]. This information can be used to place element x directly into its position in the output array B. This scheme must be modified to handle the situation in which several elements have the same value. Please see the following pseudocode for the detail:

Counting-Sort(A, B, k)
1    for i = 0 to k
2        do C[i] = 0
3    for j = 1 to length[A]
4        do C[A[j]] = C[A[j]]+1
5    /* C[i] now contains the number of elements equal to i */
6    for i = 1 to k
7    do C[i] = C[i] + C[i-1]
8    /* C[i] now contains the number of elements less than or equal to i */
9    for j = length[A] downto 1
10       do B[C[A[j]]] = A[j]
11          C[A[j]] = C[A[j]]-1

Write a program which sorts elements of given array ascending order based on the counting sort.

Input

The first line of the input includes an integer n, the number of elements in the sequence.

In the second line, n elements of the sequence are given separated by spaces characters.

Output

Print the sorted sequence. Two contiguous elements of the sequence should be separated by a space character.

Constraints

1 ≤ n ≤ 2,000,000

0 ≤ A[i] ≤ 10,000

Sample Input 1

7
2 5 1 3 2 3 0

Sample Output 1

0 1 2 2 3 3 5



Sample input:
7
2 5 1 3 2 3 0


Sample output:
0 1 2 2 3 3 5

Submission status: Wrong Answer

Solution code:
n = int(input())
l = list(map(int,input().split()))
bucket = [0]*n
for i in range(n):
    for j in range(n):
        if i == l[j]:
            bucket[i] += 1
            flg = i
for i in range(flg-1):
    for j in range(bucket[i]):
        print(i,end = ' ')
for i in range(bucket[flg]-1):
    print(flg,end=' ')
print(flg)

Submission status: Wrong Answer

Solution code:
n = int(input())
l = list(map(int,input().split()))
bucket = [0]*(n+1)
for i in range(n):
    for j in range(n):
        if i == l[j]:
            bucket[i] += 1
            flg = i
#print(bucket)
for i in range(flg):
    for j in range(bucket[i]):
        print(i,end = ' ')
for i in range(bucket[flg]-1):
    print(flg,end=' ')
print(flg)

Submission status: Wrong Answer

Solution code:
n = int(input())
l = list(map(int,input().split()))
bucket = [0]*(n+1)
for i in range(n+1):
    for j in range(n):
        if i == l[j]:
            bucket[i] += 1
            flg = i
print(bucket)
for i in range(flg):
    for j in range(bucket[i]):
        print(i,end = ' ')
for i in range(bucket[flg]-1):
    print(flg,end=' ')
print(flg)

Submission status: Wrong Answer

Solution code:
n = int(input())
l = list(map(int,input().split()))
bucket = [0]*(n+1)
for i in range(n+1):
    for j in range(n):
        if i == l[j]:
            bucket[i] += 1
            flg = i
#print(bucket)
for i in range(flg):
    for j in range(bucket[i]):
        print(i,end = ' ')
for i in range(bucket[flg]-1):
    print(flg,end=' ')
print(flg)

Submission status: Wrong Answer

Solution code:
n = int(input())
l = list(map(int,input().split()))
bucket = [0]*10000
for i in range(n):
    for j in range(n):
        if i == l[j]:
            bucket[i] += 1
            flg = i
#print(bucket)
for i in range(flg):
    for j in range(bucket[i]):
        print(i,end = ' ')
for i in range(bucket[flg]-1):
    print(flg,end=' ')
print(flg)

Submission status: Wrong Answer

Solution code:
def counting_Sort(lineA,k,n):
    lineB = []
    lineC = []

    for i in range(len(lineA)):
        lineB.append(0)

    i = 0
    while i < k:
        i = i + 1
        lineC.append(0)

    j = 1
    while j < n:
        lineC[lineA[j]] = lineC[lineA[j]] + 1
        j = j + 1

    i = 1
    while i < k:
        lineC[i] = lineC[i] + lineC[i-1]
        i = i + 1

    j = n - 1
    while j > 0:
        lineB[lineC[lineA[j]]] = lineA[j]
        lineC[lineA[j]] = lineC[lineA[j]] - 1
        j = j - 1

    return lineB



n = int(input())
lineA = list(map(int,input().split()))
if len(lineA) != n:
    print("Error")
    exit()

lineA = counting_Sort(lineA,max(lineA)+1,n)

for i in range(len(lineA)):
    if i != len(lineA):
        print(lineA[i],end=" ")
    else:
        print(lineA[i],end="")

Submission status: Wrong Answer

Solution code:
def counting_Sort(lineA,k,n):
    lineB = []
    lineC = []

    for i in range(len(lineA)):
        lineB.append(0)

    i = 0
    while i < k:
        i = i + 1
        lineC.append(0)

    j = 0
    while j < n:
        lineC[lineA[j]] = lineC[lineA[j]] + 1
        j = j + 1

    i = 1
    while i < k:
        lineC[i] = lineC[i] + lineC[i-1]
        i = i + 1

    print(n)

    j = n - 1
    while j >= 0:
        lineB[lineC[lineA[j]] - 1] = lineA[j]
        lineC[lineA[j]] = lineC[lineA[j]] - 1
        j = j - 1
        print("LineB:",end="")
        print(lineB)

    return lineB



n = int(input())
lineA = list(map(int,input().split()))
if len(lineA) != n:
    print("Error")
    exit()
print(lineA)
lineA = counting_Sort(lineA,max(lineA)+1,n)

for i in range(len(lineA)):
    if i != len(lineA):
        print(lineA[i],end=" ")
    else:
        print(lineA[i],end="")

Submission status: Wrong Answer

Solution code:
def counting_Sort(lineA,k,n):
    lineB = []
    lineC = []

    for i in range(len(lineA)):
        lineB.append(0)

    i = 0
    while i < k:
        i = i + 1
        lineC.append(0)

    j = 0
    while j < n:
        lineC[lineA[j]] = lineC[lineA[j]] + 1
        j = j + 1

    i = 1
    while i < k:
        lineC[i] = lineC[i] + lineC[i-1]
        i = i + 1

    j = n - 1
    while j >= 0:
        lineB[lineC[lineA[j]] - 1] = lineA[j]
        lineC[lineA[j]] = lineC[lineA[j]] - 1
        j = j - 1

    return lineB



n = int(input())
lineA = list(map(int,input().split()))
if len(lineA) != n:
    print("Error")
    exit()
print(lineA)
lineA = counting_Sort(lineA,max(lineA)+1,n)

for i in range(len(lineA)):
    if i != len(lineA):
        print(lineA[i],end=" ")
    else:
        print(lineA[i],end="")

Submission status: Wrong Answer

Solution code:

def partition(a, p, r):
	x = a[r]
	i = p - 1
	for j in range(p, r):
		if a[j] <= x:
			i += 1
			swap(a, i, j)
	swap(a, i + 1, r)
	return i + 1

def swap(a, i, j):
	tmp = a[i]
	a[i] = a[j]
	a[j] = tmp
	
n = int(input())
a = list(map(int, input().split()))
idx = partition(a, 0, len(a) - 1)
if idx == 0:
	print('[' + str(a[0]) + ']', end='')
else:
	print(a[0], end='')
for i in range(1, n):
	print(' ', end='')
	if idx == i:
		print('[' + str(a[i]) + ']', end='')
	else:
		print(a[i], end='')
print()

Submission status: Wrong Answer

Solution code:
def counting_sort(A, k):
    B = [0] * len(A)
    C = [0] * k

    for a in A:
        C[a] += 1

    for i in range(1, k):
        C[i] += C[i - 1]

    for a in reversed(A):
        print(a, C[a])
        B[C[a] - 1] = a
        C[a] -= 1

    return B


def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    print(*counting_sort(A, 11))


main()

Submission status: Wrong Answer

Solution code:
C = [0] * 10000
def CountingSort(A, B, k):
    #C = [0] * (k+1)
    #C[i] に i の出現数を記録する 
    for j in range(0,k):
        C[A[j]]+=1
    #print("C ",j,C[:k+1])
    #C[i] に i 以下の数の出現数を記録する
    for i in range(1,k+1):
        C[i] = C[i] + C[i-1]
    #print("C' ",j,C[:k+1])
    for j in range(k-1,-1,-1):
        B[C[A[j]]] = A[j]
        C[A[j]]-=1
        #print(j,A[j],C[A[j]],B[C[A[j]]],B,C)

n = int(input())
A = list(map(int,input().split()))
B = [0] * (n+1)
CountingSort(A,B,n)
print(' '.join(map(str,B[1:])))

Submission status: Wrong Answer

Solution code:
n = int(input())
temp = [int(i) for i in input().split()]
A = [None for i in range(200001)]
B = [0 for i in range(n)]
k = 0
for i in range(n):
    try:
        A[i] = temp[i]
        if(A[i]>k):
            k=A[i]
        if(k>10000):
            break
    except IndexError:
        break
def cntSort(A, B, k):
    C = [0 for i in range(k)]
    for j in range(0, n):
        try:
            C[A[j]] += 1
        except IndexError:
            break
    for i in range(1, k):
        try:
            C[i] += C[i-1]
        except IndexError:
            break
    for i in range(n-1, -1, -1):
        try:
            B[C[A[i]]-1] = A[i]
            C[A[i]] -= 1
        except IndexError:
            break
cntSort(A, B, k+1)
print(*B)

Submission status: Wrong Answer

Solution code:
n = int(input())
temp = [int(i) for i in input().split()]
A = [None for i in range(200001)]
B = [0 for i in range(n)]
k = 0
for i in range(n):
    try:
        A[i] = temp[i]
        if(A[i]>k):
            k=A[i]
        if(k>10000):
            break
    except IndexError:
        n = i-1
        break
def cntSort(A, B, k):
    C = [0 for i in range(k)]
    for j in range(0, n):
        C[A[j]] += 1
    for i in range(1, k):
        C[i] += C[i-1]
    for i in range(n-1, -1, -1):
        B[C[A[i]]-1] = A[i]
        C[A[i]] -= 1
cntSort(A, B, k+1)
print(*B)

Submission status: Wrong Answer

Solution code:
n = int(input())
temp = [int(i) for i in input().split()]
A = [None for i in range(200000)]
B = [0 for i in range(n)]
k = 0
for i in range(n):
    try:
        A[i] = temp[i]
        if(A[i]>k):
            k=A[i]
        if(k>10000):
            break
    except IndexError:
        n = i-1
        break
def cntSort(A, B, k):
    C = [0 for i in range(k)]
    for j in range(0, n):
        C[A[j]] += 1
    for i in range(1, k):
        C[i] += C[i-1]
    for i in range(n-1, -1, -1):
        B[C[A[i]]-1] = A[i]
        C[A[i]] -= 1
cntSort(A, B, k+1)
print(*B)

Submission status: Wrong Answer

Solution code:
n = int(input())
temp = [int(i) for i in input().split()]
A = [None for i in range(200000)]
B = [0 for i in range(n)]
k = 0
for i in range(n):
    try:
        A[i] = temp[i]
        if(A[i]>k):
            k=A[i]
        if(k>10000):
            break
    except IndexError:
        n = n-1
        break
def cntSort(A, B, k):
    C = [0 for i in range(k)]
    for j in range(0, n):
        try:
            C[A[j]] += 1
        except IndexError:
            break
    for i in range(1, k):
        C[i] += C[i-1]
    for i in range(n-1, -1, -1):
        try:
            B[C[A[i]]-1] = A[i]
            C[A[i]] -= 1
        except IndexError:
            break
cntSort(A, B, k+1)
print(*B)

Submission status: Wrong Answer

Solution code:
def InputData():
    
    sequence_len = int(input())
    sequence = [None] + [int(a) for a in input().split(" ")]

    return sequence_len, sequence

def countingSort(sequence, k, sequence_len):
    
    B = [None]*(sequence_len+1)
    C = [0]*k
    
    for j in range(1, sequence_len+1):
        C[sequence[j]] += 1
    
    for i in range(1, k):
        C[i] = C[i] + C[i-1]
    
    for j in range(sequence_len, 0, -1):
        B[C[sequence[j]]] = sequence[j]
        C[sequence[j]] -= 1

    return B

def PrintOut(sequence):
    print(' '.join( map(str, sequence)))

def main():
    [sequence_len, sequence] = InputData()
    sequence_out = countingSort(sequence, 10000, sequence_len)
    PrintOut(sequence[1:])

if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
def counting_sort(lst,ans,max):
    cnt_lst = [0] * (max+1)
    for i in range(1,len(lst)):
        cnt_lst[lst[i]] += 1
    for j in range(1,max+1):
        cnt_lst[j] = cnt_lst[j] + cnt_lst[j-1]

    for k in range(len(lst)-1,0,-1):
        ans[cnt_lst[lst[k]]] = lst[k]
        cnt_lst[lst[k]] -= 1
    return ans

n = int(input())
n_lst = list(map(int,input().split()))
ans = [0] * len(n_lst)
ans = counting_sort(n_lst,ans,max(n_lst))
print(ans)

Submission status: Wrong Answer

Solution code:
def counting_sort(lst,ans,max):
    cnt_lst = [0] * (max+1)
    for i in range(1,len(lst)):
        cnt_lst[lst[i]] += 1
    for j in range(1,max+1):
        cnt_lst[j] = cnt_lst[j] + cnt_lst[j-1]

    for k in range(len(lst)-1,0,-1):
        ans[cnt_lst[lst[k]]] = lst[k]
        cnt_lst[lst[k]] -= 1
    return ans

n = int(input())
n_lst = list(map(int,input().split()))
ans = [0] * len(n_lst)
ans = map(str,counting_sort(n_lst,ans,max(n_lst)))
print(' '.join(ans))

Submission status: Wrong Answer

Solution code:
def countingsort(a, b, k):
    c = [0 for i in range(k + 1)]
    for i in range(len(a)):
        c[a[i]] += 1
    for i in range(1, len(c)):
        c[i] += c[i - 1]
    for i in range(len(a) - 1, -1, -1):
        b[c[a[i]] - 1] = a[i]
        c[a[i]] -= 1

n = int(input())
a = list(map(int, input().split()))
b = [0] * (n + 1)
countingsort(a, b, max(a))
print(*b)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


import sys


def counting_sort(A, k):
    B = [0] * k
    C = [0] * k
    for j in range(array_length):
        C[A[j]] += 1
    print('1', C[:array_length])

    for i in range(1, k):
        C[i] += C[i - 1]
    print('2', C[:array_length])

    for m in range(array_length - 1, -1, -1):
        B[C[A[m]]] = A[m]
        C[A[m]] -= 1

    return B[1:array_length + 1]


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(int, _input[1].split()))
    assert len(array) == array_length
    MAX_ELEM = int(1e4 + 1)
    result = counting_sort(A=array, k=MAX_ELEM)
    print(*result)

Submission status: Wrong Answer

Solution code:
def CountingSort(A, B, k):
    for i in range(k+1):
        C[i] = 0

    #C[i]???i???????????°????¨??????????
    for j in range(1, n+1):
        C[A[j]] += 1

    #C[i]???i??\????????°???????????°????¨??????????
    for i in range(1, k+1):
        C[i] = C[i] + C[i-1]

    for j in range(1, n+1)[::-1]:
        B[C[A[j]]] = A[j]
        C[A[j]] -= 1


n = int(input())
A = list(map(int, input().split()))

Submission status: Wrong Answer

Solution code:
def CountingSort(A, B, k):
    C = [0 for i in range(k+1)]
    n = len(A)
    #C[i]???i???????????°????¨??????????
    for j in range(n):
        C[A[j]] += 1

    #C[i]???i??\????????°???????????°????¨??????????
    for i in range(1, k+1):
        C[i] = C[i] + C[i-1]

    for j in range(n)[::-1]:
        B[C[A[j]]] = A[j]
        print(C[A[j]])
        C[A[j]] -= 1


n = int(input())
A = list(map(int, input().split()))
B = [0 for i in range(n+1)]
CountingSort(A, B, max(A))
print(*B)

Submission status: Wrong Answer

Solution code:
def CountingSort(A, B, k):
    C = [0 for i in range(k+1)]
    n = len(A)
    #C[i]???i???????????°????¨??????????
    for j in range(n):
        C[A[j]] += 1

    #C[i]???i??\????????°???????????°????¨??????????
    for i in range(1, k+1):
        C[i] = C[i] + C[i-1]

    for j in range(n)[::-1]:
        B[C[A[j]]-1] = A[j]
        print(C[A[j]])
        C[A[j]] -= 1


n = int(input())
A = list(map(int, input().split()))
B = [0 for i in range(n)]
CountingSort(A, B, max(A))
print(*B)

Submission status: Wrong Answer

Solution code:
def CountingSort(A, B, k, n):
    C = [0 for i in range(k)]   #  for i = 0 to k { C[i] = 0 }

    # /* C[i] ??? i ???????????°????¨?????????? */
    for j in range(n):
        C[A[j]] += 1
        print("j:{} Aj:{} C[Aj]:{}".format(j,A[j], C[A[j]]))

    # /* C[i] ??? i ??\????????°???????????°????¨??????????*/
    for i in range(k):
        print("\ti:{} Ci:{} Ci-1:{}".format(i,C[i], C[i-1]))
        C[i] = C[i] + C[i-1]

    for j in reversed(range(n)):
        print("j:{} Aj:{} C[Aj]:{} k:{}".format(j,A[j], C[A[j]],k))
        B[C[A[j]]] = A[j]
        C[A[j]] -= 1

def main():
    """ ????????? """
    num = int(input().strip())
    A = list(map(int,input().split()))
    max = 0
    for i in range(num):
        if max < A[i]:
            max = A[i]
    if max < num:
        max = num
    max += 2
    B = [0 for i in range(num + 2)]
    CountingSort(A, B, max, num)
    print(" ".join(map(str,B[1:num+1])))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-


def countingSort(A, B, k, n):
    C = [0] * (k+1)

    for i in range(1, n + 1):
        C[A[i]] += 1

    for j in range(1, k + 1):
        C[j] = C[j] + C[j - 1]

    print(C)
    for j in range(n, 0, -1):
        B[C[A[j]]] = A[j]
        C[A[j]] -= 1


if __name__ == "__main__":
    n = int(input())
    lst = [int(val) for val in input().split()]
    lst.insert(0, 0)
    result = [0] * (n + 1)
    k = max(lst)
    countingSort(lst, result, k, n)
    result.pop(0)
    print(" ".join([str(val) for val in result]))

Submission status: Wrong Answer

Solution code:
def counting_sort(A, B, k):
    len_A = len(A)

    C = [0 for _ in range(k + 1)]

    for j in range(len_A):
        C[A[j]] += 1

    for i in range(1, k + 1):
        C[i] = C[i] + C[i - 1]

    for j in range(len_A - 1, -1, -1):
        B[C[A[j]] - 1] = A[j]
        C[A[j]] -= 1


n = int(input())
input_list = list(map(int, input().split(' ')))

B = [0 for _ in range(n)]

counting_sort(input_list, B, max(input_list) + 1)

print(B)

Submission status: Wrong Answer

Solution code:
def CountingSort(n, input_line, max_num):
    max_num += 1
    count_list = [0 for i in range(max_num)]
    output_line = [0 for i in range(n)]
    for i in range(n):
        count_list[input_line[i]] += 1
    for i in range(1,max_num):
        count_list[i] = count_list[i] + count_list[i-1]
    print(count_list)
    for i in range(n-1,-1, -1):
        output_line[count_list[input_line[i]]-1] = input_line[i]
        count_list[input_line[i]] -= 1
    return output_line

n = int(input())
input_line = [int(i) for i in input().split()]
max_num = max(input_line)
output_line = CountingSort(n, input_line, max_num)
print(output_line)

Submission status: Wrong Answer

Solution code:
def CountingSort(n, input_line, max_num):
    max_num += 1
    count_list = [0 for i in range(max_num)]
    output_line = [0 for i in range(n)]
    for i in range(n):
        count_list[input_line[i]] += 1
    for i in range(1,max_num):
        count_list[i] = count_list[i] + count_list[i-1]
    print(count_list)
    for i in range(n-1,-1, -1):
        output_line[count_list[input_line[i]]-1] = str(input_line[i])
        count_list[input_line[i]] -= 1
    return output_line

n = int(input())
input_line = [int(i) for i in input().split()]
max_num = max(input_line)
output_line = CountingSort(n, input_line, max_num)
print(' '.join(output_line))

Submission status: Wrong Answer

Solution code:
def countingSort(A,B,k):
    c=[]
    for i in range(k+1):
        c.append(0)

    for j in range(1,len(A)):
        c[A[j]]+=1
        
    for i in range(1,k+1):
        c[i]=c[i]+c[i-1]

    for j in range(len(A)-1,0,-1):
        B[c[A[j]]]=A[j]
        c[A[j]]-=1

n=int(input())
s=input()
l=s.split()
a=[]
b=[0 for i in range(n)]
for i in l:
    a.append(int(i))
countingSort(a,b,max(a))
for i in range(len(b)):
    print(b[i],end="");
    if i<len(b)-1:
        print(" ",end="")
print()

Submission status: Wrong Answer

Solution code:
def countingSort(A,B,k):
    c=[]
    for i in range(k+1):
        c.append(0)

    for j in range(len(A)):
        c[A[j]]+=1

    print(c)
    for i in range(1,k+1):
        c[i]=c[i]+c[i-1]

    print(c)
    for j in range(len(A)-1,-1,-1):
        B[c[A[j]]-1]=A[j]
        c[A[j]]-=1

n=int(input())
s=input()
l=s.split()
a=[]
b=[0 for i in range(n)]
for i in l:
    a.append(int(i))
countingSort(a,b,max(a))
for i in range(len(b)):
    print(b[i],end="");
    if i<len(b)-1:
        print(" ",end="")
print()

Submission status: Wrong Answer

Solution code:
n = input()

def CountingSort(a, b, k):
  for i in range(0, k):
    c[i] = 0
  for j in range (1, n):
    c[a[j]] += 1

  for i in range (1, k):
    c[i] = c[i] + c[i -1]

  for j in range(n, 1):
    b[c[a[j]]] = a[j]
    c[a[j]] -= 1

a = map(int, input().split())

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))

def countingSort(A, B, k):
    C = [0] * k
    for j in range(1, n):
        C[A[j]]+=1

    for i in range(1, k):
        C[i] = C[i] + C[i - 1]

    for j in range(1, n)[::-1]:
        B[C[A[j]]] = A[j]
        C[A[j]]-=1
    return B
        
print(countingSort(A, [0] * n, 10000))

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))

def countingSort(A, B, k):
    C = [0] * k
    for j in range(1, n):
        C[A[j]]+=1

    for i in range(1, k):
        C[i] = C[i] + C[i - 1]

    for j in range(1, n)[::-1]:
        B[C[A[j]]] = A[j]
        C[A[j]]-=1
    return B
        
print(' '.join(map(str, countingSort(A, [0] * n, 10000))))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin
from collections import Counter


def counting_sort(a, b, k):
    c = Counter()
    for j in a:
        c[j] += 1
    for i in range(k):
        c[i] += c[i-1]
    for j in a[::-1]:
        b[c[j]-1] = j
        c[j] -= 1


n = int(stdin.readline())
data = [int(s) for s in stdin.readline().split()]
output = [0] * n
counting_sort(data, output, n)
print(*output)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin
from collections import Counter


def counting_sort(a, b, k):
    c = Counter()
    for j in a:
        c[j] += 1
    for i in range(1, k+1):
        c[i] += c[i-1]
    for j in a[::-1]:
        b[c[j]] = j
        c[j] -= 1


n = int(stdin.readline())
data = [int(s) for s in stdin.readline().split()]
output = [0] * (n+1)
counting_sort(data, output, n)
print(*output[1:])

Submission status: Time Limit Exceeded

Solution code:
def counting_sort(a, b, c, k):
	for i in range(1, k+1):
		c[i] = c[i] + c[i - 1]

	for i in range(len(a) - 1, -1, -1):
		num = a[i]
		b[c[num] - 1] = num
		c[num] -= 1

n = int(input())
a = list(map(int, input().split()))
b = [0] * n
c = [0] * 10000
k = 0
for i in range(n):
	num = a[i]
	k = max(k, num)
	c[num] += 1

counting_sort(a, b, c, k)
print(b[0], end='')
for i in range(1, n):
	print(' ' +  str(b[i]), end='')
print()

Submission status: Time Limit Exceeded

Solution code:

def counting_sort(a, b, c, k):
	for i in range(1, k + 1):
		c[i] += c[i - 1]
	for i in range(len(a) - 1, -1, -1):
		c[a[i]] -= 1
		b[c[a[i]]] = a[i]
		
n = int(input())
a = list(map(int, input().split()))
b = [0] * n
c = [0] * 10000
k = 0
for i in range(n):
	c[a[i]] += 1
	k = max(k, a[i])

counting_sort(a, b, c, k)
print(b[0], end='')
for i in range(1, n):
	print(' ' + str(b[i]), end='')
print()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))

INFTY = 1000000001
cnt = [0]

def merge(left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = [0 for _ in range(n1+1)]
    R = [0 for _ in range(n2+1)]
    for i in range(n1):
        L[i] = A[left+i]
    for i in range(n2):
        R[i] = A[mid+i]
    L[n1] = INFTY
    R[n2] = INFTY
    i = 0
    j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def merge_sort(left, right):
    if left+1 < right:
        mid = int((left+right) / 2)
        merge_sort(left, mid)
        merge_sort(mid, right)
        merge(left, mid, right)

merge_sort(0, N)
print(" ".join(map(str, A)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))

INFTY = 1000000001
cnt = [0]

def merge(left, mid, right):
    L = A[left:mid]
    R = A[mid:right]
    L.append(INFTY)
    R.append(INFTY)
    i = 0
    j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def merge_sort(left, right):
    if left+1 < right:
        mid = int((left+right) / 2)
        merge_sort(left, mid)
        merge_sort(mid, right)
        merge(left, mid, right)

merge_sort(0, N)
print(" ".join(map(str, A)))

Submission status: Time Limit Exceeded

Solution code:
def counting_sort(A, B, n, k=10000):
    C = [0 for i in range(k+1)]
    for j in range(0, n):
        x = A[j]
        C[x] += 1
    for i in range(0, k+1):
        C[i] += C[i - 1]
    for j in range(n - 1, -1, -1):
        B[C[A[j]] - 1] = A[j]
        C[A[j]] -= 1

n = int(input())
A = list(map(int , input().split()))

B = [0 for i in range(n)]
for k in A:
    counting_sort(A, B, n)

print(*B)

Submission status: Time Limit Exceeded

Solution code:
import array
import sys
def counting_sort(A, B, n, k=10000):
    C = array.array('I', [0 for i in range(k+1)])
    for j in range(0, n):
        x = A[j]
        C[x] += 1
    for i in range(0, k+1):
        C[i] += C[i - 1]
    for j in range(n - 1, -1, -1):
        B[C[A[j]] - 1] = A[j]
        C[A[j]] -= 1

n = int(input())
A = list(map(int , sys.stdin.readline()[:-1].split()))

B = array.array("I", [0 for i in range(n)])
for k in A:
    counting_sort(A, B, n)

print(*B)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-


def CountingSort(A, k, n):
    B = [None]*(n+1)
    C = [A.count(i) for i in range(k)]
    for i in range(1, k):
        C[i] = C[i] + C[i-1]
    
    for j in range(n, 0, -1):
        B[C[A[j]]] = A[j]
        C[A[j]] -= 1
    
    return B


if __name__ == '__main__':
    k = 10000
    n = int(input())
    A = [None] + [int(a) for a in input().split(" ")]
    
    B = CountingSort(A, k, n)
    print(" ".join(map(str, B[1:])))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-


def CountingSort(A, k, n):
    B = [None]*(n+1)
    C = [A.count(i) for i in range(k)]
    for i in range(1, k):
        C[i] = C[i] + C[i-1]
    
    for j in range(n, 0, -1):
        B[C[A[j-1]]] = A[j-1]
        C[A[j-1]] -= 1
    
    return B


if __name__ == '__main__':
    k = 10000
    n = int(input())
    A = [int(a) for a in input().split(" ")]
    

    B = CountingSort(A, k, n)
    print(" ".join(map(str, B[1:])))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=list(map(int,input().split()))
m=max(A)+1
B=A[:]
C=[A.count(i)for i in range(m)]
for i in range(1,m):C[i]+=C[i-1]
for j in A[::-1]:B[C[j]-1]=j;C[j]-=1
print(*B)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu May  3 22:47:34 2018
ALDS1_6_A
@author: maezawa
"""

n = int(input())
a = list(map(int, input().split()))
b = [0 for _ in range(n+1)]

def counting_sort(a, b, k):
    c = [0 for _ in range(k+1)]
    
    for j in range(n):
        c[a[j]] += 1
    
    for i in range(1, k+1):
        c[i] += c[i-1]
        
    for j in reversed(range(n)):
        #print(j, a[j], c[a[j]])
        b[c[a[j]]] = a[j]
        c[a[j]] -= 1
    
k = max(a)    
counting_sort(a, b, k)
print(b[1],end='')
for i in range(2,n+1):
    print(' {}'.format(b[i]), end='')
print()

Submission status: Time Limit Exceeded

Solution code:
def countingSort(A,B,k):
    c=[]
    for i in range(k+1):
        c.append(0)

    for j in range(len(A)):
        c[A[j]]+=1
    for i in range(1,k+1):
        c[i]=c[i]+c[i-1]

    for j in range(len(A)-1,-1,-1):
        B[c[A[j]]-1]=A[j]
        c[A[j]]-=1

n=int(input())
s=input()
l=s.split()
a=[]
b=[0 for i in range(n)]
for i in l:
    a.append(int(i))
countingSort(a,b,max(a))
for i in range(len(b)):
    print(b[i],end="");
    if i<len(b)-1:
        print(" ",end="")
print()

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":
    import sys
    N = int(sys.stdin.readline().strip())
    A = [int(e) for e in sys.stdin.readline().strip().split()]
    bucket = {}
    for a in A:
        if a in bucket.keys():
            bucket[a] += 1
        else:
            bucket[a] = 1
    sortedBucket = sorted(bucket.items(), key=lambda x:x[0])
    for idx, tup in enumerate(sortedBucket):
        if idx > 0:
            sortedBucket[idx] = (tup[0], tup[1] + sortedBucket[idx-1][1])
    prevVal = 0
    for key, val in sortedBucket:
        for i in range(prevVal, val):
            A[i] = key
        prevVal = val
    print " ".join(map(str, A))

Submission status: Accepted

Solution code:
def printAns( A ):
    n = len(A)
    for i in range(1, n-1):
        print( str( A[i] ), end=" ")
    print( str( A[n-1] ) )

def main():
    n = int( input() )
    A = [0]
    list = [int(x) for x in input().split()]
    A.extend(list)
    B = []
    C = []
    k = max(A)

    for i in range(k + 1):
        C.append(0)

    for i in range(n+1):
        B.append(0)

    for j in range(1, n+1):
        C[ A[j] ] += 1

    for i in range(1, k+1):
        C[i] = C[i] + C[i-1]

    for j in reversed(range(n+1)):
        B[ C[ A[j] ] ] = A[j]
        C[ A[j] ] -= 1

    printAns(B)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
flg = 0
n = int(input())
l = list(map(int,input().split()))
bucket = [0]*10000
for i in range(n):
    bucket[l[i]] += 1
    if flg < l[i]:
        flg = l[i]
for i in range(flg):
    for j in range(bucket[i]):
        print(i,end = ' ')
for i in range(bucket[flg]-1):
    print(flg,end=' ')
print(flg)

Submission status: Accepted

Solution code:
def countingSort(A, B, k):
    C = [0 for i in range(k+1)]

    for i in A:
        C[i] += 1

    for i in range(1, k+1):
        C[i] += C[i-1]

    for i in A[::-1]:
        B[C[i]-1] = i
        C[i] -= 1

    return B


n = int(input())
A = list(map(int, input().split()))
k = max(A)
B = [0 for x in range(n)]
B = countingSort(A, B, k)
print(*B)

Submission status: Accepted

Solution code:
def counting_sort(a, b, k):
	c = [0] * (k + 1)
	for i in range(len(a)):
		c[a[i]] += 1

	for i in range(1, k+1):
		c[i] = c[i] + c[i - 1]

	for i in range(len(a) - 1, -1, -1):
		num = a[i]
		b[c[num] - 1] = num
		c[num] -= 1

n = int(input())
a = list(map(int, input().split()))
b = [0] * n
k = max(a)
counting_sort(a, b, k)
print(b[0], end='')
for i in range(1, n):
	print(' ' +  str(b[i]), end='')
print()

Submission status: Accepted

Solution code:
def counting_sort(a, b, k):
	c = [0] * (k + 1)
	for i in range(len(a)):
		c[a[i]] += 1

	for i in range(1, k+1):
		c[i] = c[i] + c[i - 1]

	for i in range(len(a) - 1, -1, -1):
		c[a[i]] -= 1
		b[c[a[i]]] = a[i]

n = int(input())
a = list(map(int, input().split()))
b = [0] * n
counting_sort(a, b, max(a))
print(b[0], end='')
for i in range(1, n):
	print(' ' +  str(b[i]), end='')
print()

Submission status: Accepted

Solution code:

def counting_sort(a, b, k):
	c = [0] * (k + 1)
	for i in range(len(a)):
		c[a[i]] += 1
	for i in range(1, k + 1):
		c[i] += c[i - 1]
	for i in range(len(a) - 1, -1, -1):
		c[a[i]] -= 1
		b[c[a[i]]] = a[i]
		
n = int(input())
a = list(map(int, input().split()))
b = [0] * n
counting_sort(a, b, max(a))
print(b[0], end='')
for i in range(1, n):
	print(' ' + str(b[i]), end='')
print()

Submission status: Accepted

Solution code:
def CountingSort(A, k):
    B = [0]*(len(A)+1)
    C = [0]*(k+1)
    for i in A:C[i]+=1
    for i in range(1,k+1):C[i]=C[i]+C[i-1]
    for i in range(n-1,-1,-1):
        B[C[A[i]]]=A[i]
        C[A[i]]-=1
    return B[1:]
n = int(input())
A = [int(i) for i in input().split()]
B = CountingSort(A,10000)
ans = ""
for i in B:ans+=str(i)+" "
print(ans[:-1])

Submission status: Accepted

Solution code:
def counting_sort(MAX):
    C = [0 for _ in range(MAX+1)]

    for i in range(N):
        C[A[i]] += 1

    for i in range(1, MAX+1):
        C[i] = C[i] + C[i-1]

    for i in range(N-1, -1, -1):
        C[A[i]] -= 1
        B[C[A[i]]] = A[i]

N = int(input())
A = list(map(int, input().split()))

MAX = 0
for n in A:
    if MAX < n:
        MAX = n

B = [0 for _ in range(N)]
counting_sort(MAX)
print(" ".join(map(str, B)))