mirror of
https://github.com/iritmaximus/tira.git
synced 2026-10-12 19:13:47 +03:00
113 lines
3.0 KiB
Python
113 lines
3.0 KiB
Python
from collections import deque
|
|
|
|
|
|
class Stack:
|
|
def __init__(self):
|
|
self.list = []
|
|
self.value_dict = {}
|
|
# print(self.list)
|
|
|
|
def push(self, x):
|
|
self.list.append(x)
|
|
# if len(self.list) - 1 not in self.value_dict:
|
|
# self.value_dict[len(self.list) - 1] = []
|
|
# print("pushed:", self.list, "--- value dict:", self.value_dict)
|
|
|
|
def pop(self):
|
|
# print()
|
|
# print("pop")
|
|
pop_value = self.list.pop()
|
|
current_list_len = len(self.list)
|
|
value_increase = 0
|
|
# print(self.list)
|
|
# print(self.value_dict)
|
|
if current_list_len not in self.value_dict:
|
|
self.value_dict[current_list_len] = []
|
|
|
|
for x in self.value_dict:
|
|
if self.value_dict[x] == []:
|
|
continue
|
|
|
|
# print("current list len:", current_list_len, "- x:", x)
|
|
|
|
if current_list_len > x:
|
|
continue
|
|
|
|
elif current_list_len < x:
|
|
value_increase += len(self.value_dict[x])
|
|
difference = x - current_list_len
|
|
|
|
for y in self.value_dict[x]:
|
|
if y - difference <= 0:
|
|
continue
|
|
self.value_dict[current_list_len].append(y - difference)
|
|
|
|
self.value_dict[x] = []
|
|
# print("dict values at x", self.value_dict[x])
|
|
|
|
# elif current_list_len == x:
|
|
# print(
|
|
# "value increased as current list len == x",
|
|
# current_list_len,
|
|
# x,
|
|
# current_list_len == x,
|
|
# )
|
|
# value_increase += len(self.value_dict[x])
|
|
|
|
# print("value dict", self.value_dict)
|
|
# print("self list", self.list)
|
|
return pop_value + value_increase
|
|
|
|
def increase(self, k):
|
|
if len(self.list) not in self.value_dict:
|
|
self.value_dict[len(self.list)] = []
|
|
|
|
self.value_dict[len(self.list)].append(k)
|
|
# print("incremented:", len(self.list), self.value_dict)
|
|
|
|
def get_len(self):
|
|
print("list", len(self.list))
|
|
print("value dict", len(self.value_dict))
|
|
|
|
|
|
if __name__ == "__main__":
|
|
s = Stack()
|
|
s.push(1)
|
|
s.push(2)
|
|
s.push(3)
|
|
s.increase(2)
|
|
print(s.pop()) # 4
|
|
s.push(1)
|
|
s.increase(2)
|
|
print(s.pop()) # 2
|
|
print(s.pop()) # 4
|
|
print(s.pop()) # 1
|
|
print()
|
|
|
|
# s = Stack()
|
|
# s.push(1)
|
|
# s.push(2)
|
|
# s.push(3)
|
|
# s.increase(2)
|
|
# s.increase(2)
|
|
# print(s.pop())
|
|
# print(s.pop())
|
|
s = Stack()
|
|
for i in range(5 * 10**4):
|
|
s.push(i + 1)
|
|
for i in range(5 * 10**4 - 1):
|
|
s.increase(5 * 10**4)
|
|
# print(s.pop())
|
|
s = Stack()
|
|
for i in range(14000):
|
|
for j in range(3):
|
|
s.push(i * i + 1)
|
|
s.increase(i + 1)
|
|
# print(s.pop())
|
|
s.pop()
|
|
s.get_len()
|
|
for i in range(28000):
|
|
# print(s.pop())
|
|
s.pop()
|
|
s.get_len()
|