In [1]:
# Version 2
# Passes all test cases
In [2]:
# read in N,M
fin = open ('cereal.in', 'r')
fout = open ('cereal.out', 'w')
# N = Cows
# M = Cereals
N,M = map(int, fin.readline().split())
print(N,M)
In [3]:
# read in first choice, second choice
choice1 = []
choice2 = []
# subtract 1 so cereal index is 0 to M-1
for i in range(N):
a,b = map(int,fin.readline().split())
choice1.append(a-1)
choice2.append(b-1)
# print out choice lists
# for a,b in zip(choice1,choice2):
# print(a,b)
In [4]:
ans = [0]*N
# Now the simulation is running backwards, generating the answer for the last cow
# and then adding one cow at a time. The answer for each line will be the answer
# from the previous line plus 1 IF A NEW CEREAL IS USED when the new cow is added.
# Otherwise, the current answer is the same as the previous answer.
cereal = [-1]*M # check if cereal has been consumed, ALSO Keep Track of Which Cow Got That Cereal.
# initialize with last (N-1) cow, who will get her choice1 initially
c1 = choice1[N-1]
cereal[c1]=N-1
ans[N-1] = 1
# This function checks if a new cereal is used when the new cow is added
# the new cow will get her first choice -- if this is an unused cereal return True
# otherwise, this may bump other cows from first choice to second choice, which
# might also be a new cereal. If no new cereal is used, return False.
def new_cereal_assigned(cow):
c1 = choice1[cow]
c2 = choice2[cow]
if cereal[c1] == -1:
cereal[c1] = cow
return True
if cereal[c1]<cow:
if cereal[c2] == -1:
cereal[c2] = cow
return True
if cereal[c2]<cow:
return False
bumpcow = cereal[c2]
cereal[c2] = cow
return new_cereal_assigned(bumpcow)
bumpcow = cereal[c1]
cereal[c1] = cow
return new_cereal_assigned(bumpcow)
# Loop starting with the second to last cow (N-1) work backwards, adding cows to the front
# adjust answer if new cereal is used
for j in range(N-2,-1,-1):
if new_cereal_assigned(j):
ans[j]=ans[j+1]+1
else:
ans[j]=ans[j+1]
print(ans)
for i in range(N):
fout.write(str(ans[i])+"\n")
fout.close()
