from os import remove
import sys
import time
class HoaresAlgoSort:
def sort(self, array):
self.qsort(array, 0, len(array) - 1)
return array
def qsort(self, array, low, high):
if low < high:
pivot = self.partition(array, low, high)
self.qsort(array, low, pivot)
self.qsort(array, pivot + 1, high)
def partition(self, array, low, high):
pivot = array[(low + high) // 2]
i, j = low, high
while True:
while array[i] > pivot:
i += 1
while array[j] < pivot:
j -= 1
if i >= j:
return j
array[i], array[j] = array[j], array[i]
i += 1
j -= 1
class customSort:
def countingSort(self, array):
size = len(array)
output = [0 for i in range(size)]
max = self.getMax(array, size)
temp = [0 for i in range(max+1)]
for i in range(max):
temp[i] = 0
for j in range(size):
temp[int(array[j])] += 1
j = 0
for num in range(max, -1, -1):
while (temp[num] > 0):
temp[num] -= 1
output[j] = num
j += 1
for i in range(size):
array[i] = output[i]
return array
def getMax(self, array, n):
max = array[0]
for i in range(1, n):
if (array[i] > max):
max = array[i]
return max
def main():
SKILL_BREAKDANCING, SKILL_APICULTURE, SKILL_BASKET, SKILL_XBASKET, SKILL_SWORD, TOTAL_XP = [], [], [], [], [], []
TEMP_BREAKDANCING, TEMP_APICULTURE, TEMP_BASKET, TEMP_XBASKET, TEMP_SWORD, TEMP_TOTAL_XP = [], [], [], [], [], []
temp = 0
for line in sys.stdin: # Read in numbers and put into lists
num = line.split()
if (int(num[0]) > 2000):
TEMP_BREAKDANCING.append(int(num[0]))
TEMP_APICULTURE.append(int(num[1]))
TEMP_BASKET.append(int(num[2]))
TEMP_XBASKET.append(int(num[3]))
TEMP_SWORD.append(int(num[4]))
temp = sum(map(int, num))
TEMP_TOTAL_XP.append(temp)
else:
SKILL_BREAKDANCING.append(int(num[0]))
SKILL_APICULTURE.append(int(num[1]))
SKILL_BASKET.append(int(num[2]))
SKILL_XBASKET.append(int(num[3]))
SKILL_SWORD.append(int(num[4]))
temp = sum(map(int, num))
TOTAL_XP.append(temp)
temp = 0
custom_sorter = customSort()
big_num_sorter = HoaresAlgoSort()
start_time = time.time_ns()
custom_sorter.countingSort(SKILL_BREAKDANCING)
big_num_sorter.sort(TEMP_BREAKDANCING)
TEMP_BREAKDANCING += SKILL_BREAKDANCING
BREAKDANCING_time_taken_in_microseconds = (time.time_ns() - start_time) / 1000.0
print('SKILL_BREAKDANCING')
for num in TEMP_BREAKDANCING:
print(num)
print('time taken: ' + str(BREAKDANCING_time_taken_in_microseconds) + '\n')
start_time = time.time_ns()
custom_sorter.countingSort(SKILL_APICULTURE)
big_num_sorter.sort(TEMP_APICULTURE)
TEMP_APICULTURE += SKILL_APICULTURE
APICULTURE_time_taken_in_microseconds = (time.time_ns() - start_time) / 1000.0
print('SKILL_APICULTURE')
for num in TEMP_APICULTURE:
print(num)
print('time taken: ' + str(APICULTURE_time_taken_in_microseconds) + '\n')
start_time = time.time_ns()
custom_sorter.countingSort(SKILL_BASKET)
big_num_sorter.sort(TEMP_BASKET)
TEMP_BASKET += SKILL_BASKET
BASKET_time_taken_in_microseconds = (time.time_ns() - start_time) / 1000.0
print('SKILL_BASKET')
for num in TEMP_BASKET:
print(num)
print('time taken: ' + str(BASKET_time_taken_in_microseconds) + '\n')
start_time = time.time_ns()
custom_sorter.countingSort(SKILL_XBASKET)
big_num_sorter.sort(TEMP_XBASKET)
TEMP_XBASKET += SKILL_XBASKET
XBASKET_time_taken_in_microseconds = (time.time_ns() - start_time) / 1000.0
print('SKILL_XBASKET')
for num in TEMP_XBASKET:
print(num)
print('time taken: ' + str(XBASKET_time_taken_in_microseconds) + '\n')
start_time = time.time_ns()
custom_sorter.countingSort(SKILL_SWORD)
big_num_sorter.sort(TEMP_SWORD)
TEMP_SWORD += SKILL_SWORD
SWORD_time_taken_in_microseconds = (time.time_ns() - start_time) / 1000.0
print('SKILL_SWORD')
for num in TEMP_SWORD:
print(num)
print('time taken: ' + str(SWORD_time_taken_in_microseconds) + '\n')
start_time = time.time_ns()
custom_sorter.countingSort(TOTAL_XP)
big_num_sorter.sort(TEMP_TOTAL_XP)
TEMP_TOTAL_XP += TOTAL_XP
TOTAL_XP_time_taken_in_microseconds = (time.time_ns() - start_time) / 1000.0
print('TOTAL_XP')
for num in TEMP_TOTAL_XP:
print(num)
print('time taken: ' + str(TOTAL_XP_time_taken_in_microseconds))
print('total time taken: ' + str(BREAKDANCING_time_taken_in_microseconds + APICULTURE_time_taken_in_microseconds + BASKET_time_taken_in_microseconds + XBASKET_time_taken_in_microseconds + SWORD_time_taken_in_microseconds + TOTAL_XP_time_taken_in_microseconds))
if __name__ == '__main__':
main()