Submission #58038450

---

Source Code Expand

N,M,Q = gets.split.map(&:to_i) # 1000,10,950
Ask,Ans = lambda{
if $debug
	Coins = -1,*[*[1]*M,*[0]*(N-M)].shuffle
end
	qc = 0
	next lambda{|x,y|
		if Q<qc += 1
			warn 'QC over'
			exit 1
		end
		if [x,y].any?{|x| x<1||N<x }
			warn "Invalid coins (#{x},#{y}) "
			exit 1
		end
if $debug
		a = "#{Coins[x]^Coins[y]}"
else
		puts "? #{x} #{y}"
		$stdout.flush
		a = gets[0]
end
		next 0 if a==?0
		next 1 if a==?1
		warn "Rejected"
		exit 1
	},lambda{|as|
		warn "Answered (#{as.sort*?,})"
		puts [?!,*as]*' '
if $debug
		warn "Answer   (#{(1..N).select{|i| 0<Coins[i] }*?,})"
end
		exit 0
	}
}.call
F = lambda{|n,m,hint=nil| # n:1..N; m:0..M
	k = N-n+1
	b = [m,[k-m,10].min].min
	cs,ol = [0],[1,0]
	until b<ol.max || cs.size==k
		cs.push cs[-1]^Ask[n+cs.size-1,n+cs.size]
		ol[cs[-1]] += 1
	end
	if m<k-m || 10<ol.max # 多数派が偽物ではありえないほど多くなった
		cs.map!{|c| 1-c } unless b<ol[0]
	elsif k-m<m # 多数が本物ではありえないほど多くなった
		cs.map!{|c| 1-c } unless b<ol[1]
	else # 同数
		cs.map!{|c| 1-c } if 1==Ask[hint,n+cs.index(1)]
	end
	next cs
}
C,OI,hint = [-1],[0,0]
C.concat F[C.size,M-OI[1],hint].tap{|cs|
	i = cs.index 1
	hint ||= C.size+i if i
	cs.each{|c| OI[c] += 1 }
} until N<C.size
Ans[(1..N).select{|i| 0<C[i] }]

Submission Info

Judge Result