Ehab and another another xor problem

Explicación

Una buena estrategia para atacar estos problemas es simular e intentar detectar un patrón. Además, hay que tener en cuenta qué importa en cada paso y construir casos alrededor de eso. Por último, procesar las consultas de forma que se puedan distinguir todos los casos.

Aquí, podemos consultar del bit más significativo al menos significativo. Esto es porque, en operaciones bit a bit, como los bits más altos siempre tienen prioridad, es difícil eludir el efecto de los bits más altos si no se conocen ya.

Primero, podemos enviar una consulta $(c, d) = (0, 0)$ para saber si $a$ o $b$ es mayor (esto será útil más adelante). Ahora, recorremos de los bits más significativos a los menos significativos. Sean $\mathtt{curA}$ y $\mathtt{curB}$ los valores de los bits de $a$ y $b$ que ya conocemos. Podemos intentar distinguir los dos números en este bit. Enviamos dos consultas, de la forma $(\mathtt{curA}| 2^B, \mathtt{curB})$ , y $(\mathtt{curA}, \mathtt{curB} | 2^B)$ donde estamos recorriendo el bit $B$ . También sabemos que hay los siguientes cuatro casos a considerar:

Tanto $a$ como $b$ tienen el bit $B$ activado
Ni $a$ ni $b$ tienen el bit $B$ activado
Solo $a$ tiene el bit $B$ activado
Solo $b$ tiene el bit $B$ activado

En los primeros dos casos, los resultados de las dos consultas serán distintos. Esto es porque, como usamos XOR sobre un bit activado en un número y no en el otro, siempre habrá una consulta mayor, ya que tienen el mismo bit en esta posición. Si la primera consulta da $-1$ o la segunda da $1$ , tanto $a$ como $b$ deben tener el bit $B$ activado.

Así, para los últimos dos casos, los resultados de las dos consultas serán distintos. Para distinguir qué número tomará el bit, ¡recordemos que ya sabemos cuál es mayor hasta ahora! En este caso, el número mayor debe tomar este bit; si no, el menor lo tomaría y eso lleva a una contradicción porque los bits más altos tienen prioridad. Ahora, hay que actualizar cuál es mayor según nuestra consulta actual para quitar el efecto de los bits más significativos.

Implementación

Complejidad temporal: $\mathcal{O}(1)$

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
int ask(int a, int b) {
	cout << "? " << a << " " << b << endl;
	int res;
	cin >> res;
	return res;
}
 
int main() {
	bool a_greater_than_b = ask(0, 0) == 1;
	int a = 0;
	int b = 0;
	// 2^29 es el bit máximo por las restricciones
	for (int bit = 29; bit >= 0; bit--) {
		int query1 = ask(a | (1 << bit), b);
		int query2 = ask(a, b | (1 << bit));
		if (query1 != query2) {
			if (query1 == -1) {
				// caso 1
				a |= 1 << bit;
				b |= 1 << bit;
			}
			// caso 2 (no hacemos nada)
		} else {
			if (a_greater_than_b) {
				// caso 3
				a |= 1 << bit;
			} else {
				// caso 4
				b |= 1 << bit;
			}
			a_greater_than_b = query1 == 1;
		}
	}
 
	cout << "! " << a << " " << b << endl;
}


import java.io.*;
import java.util.*;
 
public class EhabAndXOR {
	public static void main(String[] args) {
		Kattio io = new Kattio();
 
		boolean aGreaterThanB = (ask(0, 0) == 1 ? true : false);
		int a = 0;
		int b = 0;
 
		// 2^29 es el bit máximo por las restricciones
		for (int bit = 29; bit >= 0; bit--) {
			int query1 = ask(a | (1 << bit), b);
			int query2 = ask(a, b | (1 << bit));
 
			if (query1 != query2) {
				if (query1 == -1) {
					// caso 1
					a |= 1 << bit;
					b |= 1 << bit;
				}
				// caso 2 (no hacemos nada)
			} else {
				if (aGreaterThanB) {
					// caso 3
					a |= 1 << bit;
				} else {
					// caso 4
					b |= 1 << bit;
				}
				aGreaterThanB = (query1 == 1 ? true : false);
			}
		}
 
		io.println("! " + a + " " + b);
		io.flush();
		io.close();
	}
 
	private static int ask(int a, int b) {
		Kattio io = new Kattio();
		io.println("? " + a + " " + b);
		io.flush();
		int res = io.nextInt();
		return res;
	}
 
	// CodeSnip{Kattio}
}


def ask(a: int, b: int):
	print(f"? {a} {b}")
	res = int(input())
	return res
 
 
a_greater_than_b = ask(0, 0) == 1
a, b = 0, 0
 
# 2^29 es el bit máximo por las restricciones
for bit in range(29, -1, -1):
	query1 = ask(a | (1 << bit), b)
	query2 = ask(a, b | (1 << bit))
 
	if query1 != query2:
		if query1 == -1:
			# caso 1
			a |= 1 << bit
			b |= 1 << bit
 
		# caso 2 (no hacemos nada)
 
	else:
		if a_greater_than_b:
			# caso 3
			a |= 1 << bit
 
		else:
			# caso 4
			b |= 1 << bit
 
		a_greater_than_b = query1 == 1
 
print(f"! {a} {b}")