Submission #43229224

---

Source Code Expand

class Stat
	def initialize m
		@m = m
		@x = {}
		@xs = {}
	end

	def conflict?
		! @xs.empty?
	end
	def each_pair &block
		Enumerator.new{|y|
			@xs.each_value{|xs|
				xs.keys.combination(2){|xx|
					y<<xx
				}
			}
		}.each(&block)
	end

	def put x
		pfx = @m&x
		if xs = @xs[pfx]
			xs[x] = x
		elsif y = @x[pfx] and x!=y
			@x.delete pfx
			@xs[pfx] = {x=>x, y=>y}
		else
			@x[pfx] = x
		end
	end
	def del x
		pfx = @m&x
		if xs = @xs[pfx]
			xs.delete x
			y, = xs.shift if xs.size==1
			@xs.delete pfx if xs.empty?
			@x[pfx] = y if y
		elsif @x[pfx]==x
			@x.delete pfx
		else
			# put してない x を del しようとした。
		end
	end
end

A = []
S = [Stat.new(m = (1<<30)-1)]
S.push Stat.new m &= m-1 while 0<m
X = Hash.new xx = 0
gets.to_i.times{
	c,x = gets.split.map(&:to_i)
	case c
	when 1
		xx += 1 if 2==X[x] += 1
		S.each{|st| st.put x } if 1==X[x]
	when 2
		xx -= 1 if 1==X[x] -= 1
		S.each{|st| st.del x } if 0==X[x]
	else
		A.push 0<xx ? 0 : S.find(&:conflict?).each_pair.map{_1^_2}.min
	end
}

puts A

Submission Info

Judge Result