Ois_annoluce 60/100

Aiuto
1

Oggi mi sono trovato alle prese con il problema annoluce

Ho fatto molta attenzione a non andare in overflow con le variabili, ma purtroppo i testcase 4, 5 e 24 mi escono ancora come output sbaglato.
Sto ordinando il vettore distanze e utilizzando la ricerca binaria per cercare il risultato. Credo che sia la mia implementazione della ricerca binaria il problema, perché se provo ad utilizzare la ricerca lineare, i testcase 4 e 5 automaticamente saltano corretti (il 24 va in timeout).

int binarySearch(unsigned long long &query, vector<unsigned long long> &distances, int &N) {
	unsigned long long target = (uint64_t)query * (uint64_t)query;
	int left = 0;
	int right = N - 1;
	while (left <= right) {
		int mid = (left + right) / 2;
		if (distances[mid] <= target && distances[mid + 1] > target)
			return mid;

		if (distances[mid] < target) {
			left = mid + 1;
		} else {
			right = mid - 1;
		}
	}
	return -1;
}

Questa é la mia implementazione della ricerca binaria (iterativa). Query viene elevato alla seconda perché le distanze le salvo senza metterle sotto radice, e quindi devo trovare D alla seconda invece di solo D.

2

Hai tenuto presente che potrebbero esserci più stelle alla stessa distanza?
La ricerca lineare potrebbe non andare in time out se ordini anche le query …

3

Se sei confuso sull’implementazione della ricerca binaria ti consiglio questo post.

1 Mi Piace
4

Il problema potrebbe essere il seguente:
distances[mid]=target ma anche distances[mid+1]=target
in tal caso si salta il primo if e si fa l’else del secondo!!
forse funziona modificando il secondo if in

if (distances[mid] <= target)

5

grazie mille! la mia ricerca binaria non teneva in caso questo edge case