fork download
copy 
  1. from os import remove
  2. import sys
  3. import time
  4.  
  5. class HoaresAlgoSort:        
  6.     def sort(self, array):
  7.         self.qsort(array, 0, len(array) - 1)
  8.         return array
  9.     def qsort(self, array, low, high):
  10.         if low < high:
  11.             pivot = self.partition(array, low, high)
  12.             self.qsort(array, low, pivot)
  13.             self.qsort(array, pivot + 1, high)
  14.     def partition(self, array, low, high):
  15.         pivot = array[(low + high) // 2]
  16.         i, j = low, high
  17.         while True:
  18.             while array[i] > pivot:
  19.                 i += 1
  20.             while array[j] < pivot:
  21.                 j -= 1
  22.             if i >= j:
  23.                 return j
  24.             array[i], array[j] = array[j], array[i]
  25.             i += 1
  26.             j -= 1
  27.  
  28. class customSort:
  29.     def countingSort(self, array):
  30.         size = len(array)
  31.         output = [0 for i in range(size)]
  32.         max = self.getMax(array, size)
  33.         temp = [0 for i in range(max+1)]
  34.         for i in range(max):
  35.             temp[i] = 0
  36.         for j in range(size):
  37.             temp[int(array[j])] += 1
  38.         j = 0
  39.         for num in range(max, -1, -1):
  40.             while (temp[num] > 0):
  41.                 temp[num] -= 1
  42.                 output[j] = num
  43.                 j += 1
  44.         for i in range(size):
  45.             array[i] = output[i]
  46.         return array
  47.  
  48.     def getMax(self, array, n):
  49.         max = array[0]
  50.         for i in range(1, n):
  51.             if (array[i] > max):
  52.                 max = array[i]
  53.         return max
  54.  
  55. def main():
  56.     SKILL_BREAKDANCING, SKILL_APICULTURE, SKILL_BASKET, SKILL_XBASKET, SKILL_SWORD, TOTAL_XP = [], [], [], [], [], []
  57.     TEMP_BREAKDANCING, TEMP_APICULTURE, TEMP_BASKET, TEMP_XBASKET, TEMP_SWORD, TEMP_TOTAL_XP = [], [], [], [], [], []
  58.     temp = 0
  59.     for line in sys.stdin: # Read in numbers and put into lists
  60.         num = line.split()
  61.         if (int(num[0]) > 2000):
  62.             TEMP_BREAKDANCING.append(int(num[0]))
  63.             TEMP_APICULTURE.append(int(num[1]))
  64.             TEMP_BASKET.append(int(num[2]))
  65.             TEMP_XBASKET.append(int(num[3]))
  66.             TEMP_SWORD.append(int(num[4]))
  67.             temp = sum(map(int, num))
  68.             TEMP_TOTAL_XP.append(temp)
  69.         else:
  70.             SKILL_BREAKDANCING.append(int(num[0]))
  71.             SKILL_APICULTURE.append(int(num[1]))
  72.             SKILL_BASKET.append(int(num[2]))
  73.             SKILL_XBASKET.append(int(num[3]))
  74.             SKILL_SWORD.append(int(num[4]))
  75.             temp = sum(map(int, num))
  76.             TOTAL_XP.append(temp)
  77.         temp = 0
  78.     custom_sorter = customSort()
  79.     big_num_sorter = HoaresAlgoSort()
  80.     start_time = time.time_ns()
  81.     custom_sorter.countingSort(SKILL_BREAKDANCING)
  82.     big_num_sorter.sort(TEMP_BREAKDANCING)
  83.     TEMP_BREAKDANCING += SKILL_BREAKDANCING
  84.     BREAKDANCING_time_taken_in_microseconds = (time.time_ns() - start_time) / 1000.0
  85.     print('SKILL_BREAKDANCING')
  86.     for num in TEMP_BREAKDANCING:
  87.         print(num)
  88.     print('time taken: ' + str(BREAKDANCING_time_taken_in_microseconds) + '\n')
  89.     start_time = time.time_ns()
  90.     custom_sorter.countingSort(SKILL_APICULTURE)
  91.     big_num_sorter.sort(TEMP_APICULTURE)
  92.     TEMP_APICULTURE += SKILL_APICULTURE
  93.     APICULTURE_time_taken_in_microseconds = (time.time_ns() - start_time) / 1000.0
  94.     print('SKILL_APICULTURE')
  95.     for num in TEMP_APICULTURE:
  96.         print(num)
  97.     print('time taken: ' + str(APICULTURE_time_taken_in_microseconds) + '\n')
  98.     start_time = time.time_ns()
  99.     custom_sorter.countingSort(SKILL_BASKET)
  100.     big_num_sorter.sort(TEMP_BASKET)
  101.     TEMP_BASKET += SKILL_BASKET
  102.     BASKET_time_taken_in_microseconds = (time.time_ns() - start_time) / 1000.0
  103.     print('SKILL_BASKET')
  104.     for num in TEMP_BASKET:
  105.         print(num)
  106.     print('time taken: ' + str(BASKET_time_taken_in_microseconds) + '\n')
  107.     start_time = time.time_ns()
  108.     custom_sorter.countingSort(SKILL_XBASKET)
  109.     big_num_sorter.sort(TEMP_XBASKET)
  110.     TEMP_XBASKET += SKILL_XBASKET
  111.     XBASKET_time_taken_in_microseconds = (time.time_ns() - start_time) / 1000.0
  112.     print('SKILL_XBASKET')
  113.     for num in TEMP_XBASKET:
  114.         print(num)
  115.     print('time taken: ' + str(XBASKET_time_taken_in_microseconds) + '\n')
  116.     start_time = time.time_ns()
  117.     custom_sorter.countingSort(SKILL_SWORD)
  118.     big_num_sorter.sort(TEMP_SWORD)
  119.     TEMP_SWORD += SKILL_SWORD
  120.     SWORD_time_taken_in_microseconds = (time.time_ns() - start_time) / 1000.0
  121.     print('SKILL_SWORD')
  122.     for num in TEMP_SWORD:
  123.         print(num)
  124.     print('time taken: ' + str(SWORD_time_taken_in_microseconds) + '\n')
  125.     start_time = time.time_ns()
  126.     custom_sorter.countingSort(TOTAL_XP)
  127.     big_num_sorter.sort(TEMP_TOTAL_XP)
  128.     TEMP_TOTAL_XP += TOTAL_XP
  129.     TOTAL_XP_time_taken_in_microseconds = (time.time_ns() - start_time) / 1000.0
  130.     print('TOTAL_XP')
  131.     for num in TEMP_TOTAL_XP:
  132.         print(num)
  133.     print('time taken: ' + str(TOTAL_XP_time_taken_in_microseconds))
  134.     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))
  135.  
  136. if __name__ == '__main__':
  137.     main()
Success #stdin #stdout 0.03s 9516KB
comments (?)
stdin
copy 
1445 1984 652 1817 1189
444 1279 1919 1093 1729
275 1411 1655 112 520
40249492 20774929 38227558 80183545 29549102
1784 1509 1773 384 1102
1956 1267 1558 1599 1495
808 920 1884 1432 520
376 1714 1375 165 602
290 1603 1462 1261 873
1198 1072 531 1217 1785
stdout
copy 
SKILL_BREAKDANCING
40249492
1956
1784
1445
1198
808
444
376
290
275
time taken: 261.891

SKILL_APICULTURE
20774929
1984
1714
1603
1509
1411
1279
1267
1072
920
time taken: 267.379

SKILL_BASKET
38227558
1919
1884
1773
1655
1558
1462
1375
652
531
time taken: 257.549

SKILL_XBASKET
80183545
1817
1599
1432
1261
1217
1093
384
165
112
time taken: 232.059

SKILL_SWORD
29549102
1785
1729
1495
1189
1102
873
602
520
520
time taken: 227.169

TOTAL_XP
208984626
7875
7087
6552
6464
5803
5564
5489
4232
3973
time taken: 1017.757
total time taken: 2263.804
https://ideone.com/x4X9jR
language:
Python 3 (python  3.9.5)
created:
1 year 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!