missingnumber.cpp

#include <bits/stdc++.h>
using namespace std;


int n;
set<int> global;

int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) global.insert(i); //inserimos todos os indices de 1 à n no set global

	set<int>::iterator it;
	int pergunta = 0, resp = 0; // resp será o numero de fora

	for(int i = 0; global.size() > 0; i++){ // enquanto ainda existir algum elemento do set, passaremos pelo i-ésimo bit
		
		
		set<int> local;
		for(it = global.begin(); it!=global.end(); it++){
			int numeroatual = *it;
			cout << "? " << numeroatual << " "<< i << endl; 
			cout.flush();
			cin >> pergunta; // verificamos se o indice atual tem o i-ésimo bit ativo
			
			if(pergunta) local.insert(numeroatual); // inserimos no set local todos os indíces 
													// com o i-ésimo bit ativo em seu respectivo número

	
			

		}
		int mid = (global.size() + 1)/2;
		//	caso existam menos que o (tamanho do set global + 1)/2 números com o i-ésimo
		//	bit ativo, com certeza o número de fora tem o i-ésimo bit ativo

		if(local.size() < mid){

			resp += (1<<i);
			global = local;
			
		}
		// caso contrário, temos que retirar todos os indíces 
		// com o i-ésimo bit ativo em seu respectivo número do set global

		else{
			
			for(it = local.begin(); it!=local.end(); it++){
				int esse  = *it;
				global.erase(esse);

			}
		}
	}

	cout << "! " << resp << endl; // imprimimos a resposta
	cout.flush();
}