N = int(input())
S = set(input() for i in range(N))
for s in S:
if "!" + s in S:
print(s)
exit()
print("satisfiable")
x in list is computational complexity order O (N) x in set can be easily melted by using the fact that the complexity order is O (1). The reason seems to be that the set type data puts each value in a function called a hash function and connects the values that come out. The following article was easy to understand, so I will post a link
Refer to the above article and give an easy-to-understand example of how x in set works internally. Consider whether the element of set = {23,7,11,4,10} contains 9. Considering a hash function with hash (x) = x% 5 Since hash (23) = 3, hash (7) = 2, hash (11) = 1, hash (4) = 4, hash (10) = 0 Stores 10 in the memory address 0, 11 in the 1st address, 7 in the 2nd address, 23 in the 3rd address, and 4 in the 4th address.
Since hash (9) = 4 here, check the number stored in the memory at address 4. As a result, it can be seen that 9 is not included in the set because the number contained is 4 and not 9.
In the above example, in the list, it can be seen that the value had to be confirmed at all addresses 1 to 4, but by using set, only address 4 had to be confirmed.
In this contest, I stumbled upon this problem and melted it for about 40 minutes. I couldn't solve it without such knowledge of the problem, so I should have rounded it up. If it's an inspirational problem, it may be solved by taking time, but if it's a knowledge problem, it's impossible. However, I don't know if the problem I'm solving is a knowledge problem or a flash problem, so if I can't do it for 30 minutes, I'll skip it and move on to the next problem.
Recommended Posts