Binary search – co jest nie tak w moim algorytmie?

Siema, co jest tutaj nie tak? Kompletnie już jestem wkurzony, bo ciągle wychodzą jakieś nowe błędy, poprawiam go już masę czasu, napiszcie co jest nie tak.

„Dany jest worek. Jest to tzw. „worek kombinatoryczny”, czyli oczywiście znajdują się w nim kule. Na każdej kuli napisany jest jakiś numer. Grupa kombinatoryków chce zbadać własności multizbioru modelowanego za pomocą tegoż worka. W tym celu potrzebują znać odpowiedzi na „kilka” zapytań po staci „ile jest kul o numerze x Twoim zadaniem jest udzielić (poprawnych) odpowiedzi na te zapytania.

Wejście:

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita n (0<=n<=1 000 000), oznaczająca liczbę kul w worku. W kolejnym wierszu znajduje się n liczb całkowitych należących do przedziału 〈0; 10^18〉 oznaczających numery na kulach. W kolejnym wierszu znajduje się jedna liczba całkowita q (1<=q<=100 000) oznaczająca liczbę zapytań. W każdym z kolejnych q wierszy znajduje się jedna liczba całkowita x (0<=x<=10^18 + 1), oznaczająca numer, którego wystąpienia w worku należy zliczyć.

Wyjście:

Dla każdego z q zapytań należy w osobnej linii wypisać policzoną liczbę kul

#include<algorithm>
#include<iostream>
using namespace std;
long long numery[1000009];//przechowuje numery na kulach
long long licznosci[1000009];//jeśli algorytm policzył ile jest kul o numerze Z to zapisuje to do licznosci[Z] i przy nastepnym takim zapytaniu program już tego nie liczy tylko pobiera
int main()
{
	int n;//liczba kul w worku
	long long x;//numer którego chcemy sprawdzić liczność
	int min;//najmniejszy indeks posortowanej numery[] równy x
	int max;//najmniejszy indeks posortowanej numery[] większy od x
	int i;//indeks w działaniu algorytmu ograniczający przedział poszukiwań od dołu
	int j;indeks w działaniu algorytmu ograniczający przedział poszukiwań od góry
	int q;//liczba zapytań o występowanie danego numeru
	cin>>n;//liczba kul w worku
	for(int i=0;i<1000000;i++)//ponieważ numery zaczynają się od 0 łątwo sprawdzić, że jeśli jest -10 to po prostu jest to pierwsze zapytanie o ten numer
	{
		licznosci[i]=-10;
	}
	for(int i=0;i<n;i++)//pobranie numerów na kulach
	{
		cin>>numery[i];
	}
	sort(numery,numery+n);
	cin>>q;
	while(q>0)
	{
		cin>>x;
		{
			min=0;
			max=0;
			i=0;//na początku bierzemy cały zakres, 'i' oraz 'j' ustawiamy na punkty krańcowe
			j=n-1;
			if(numery[n-1]<x)//jeśli największy numer jest mniejszy od x to na pewno nie ma go na żadnej kuli
			{
				i=-10;//wypisujemy -10, bo takiego indeksu nie ma i łatwo potem ograniczyć jakimś warunkiem
			}
			else if(licznosci[x]!=-10)//jeśli już było zapytanie o ten numer to algorytm po prostu go odczyta
			cout<<licznosci[x];
			else
			{
				while(j-i>1)//poszukujemy najmniejszego  indeksu przy którym numery[min]==x
				{
					if(numery[(j-i)/2+i]<x)//jeśli indeks w połowie aktualnego przedziału poszukiwań jest<x to ograniczamy tam lewostronnie przedział
					i=(j-i)/2+i;
					else//jeśli nie to ustawiamy tam j ograniczające następny przedział prawostronnie
					j=(j-i)/2+i;
				}
				if(numery[i]==x)//tutaj nie wiem czy te warunki są potrzebne
				min=i;
				else if(numery[i+1]==x)
				min=i+1;
				else
				i=-10;
			}
			if(i!=-10)
			{//tutaj poszukujemy najmniejszego max gdzie zachodzi numery[max]>x lub w przypadku gdy numery[n-1]==x to ustawiamy max=n
				i=min;//ustawiamy lewą granicę przedziału na min, bo na pewno wcześniej nie znajdziemy takiego max
				j=n-1;
				while(j-i>1)
				{
					if(numery[(j-i)/2+i]==x)
					i=(j-i)/2+i;
					else
					j=(j-i)/2+i;
				}
				if(numery[j]==x)//tutaj też nie wiem czy potrzebne te warunki, ale dałem dla pewności
				max=j+1;
				else
				max=j;
				cout<<max-min;
				licznosci[x]=max-min;
			}
			else
			{
				cout<<0;
				licznosci[x]=0;	
			}
		}
		cout<<"\n";
		q--;
	}
	return 0;
}

Czy nie byłbyś w stanie użyć do tego zadania unordered map? Nie znam się na c++, ale wydaje mi się że ta struktura od razu rozwiązuje Ci problem.

kapojot napisał(a):

Czy nie byłbyś w stanie użyć do tego zadania unordered map? Nie znam się na c++, ale wydaje mi się że ta struktura od razu rozwiązuje Ci problem.

@kapojot, @pawel1216: W zadaniu napisane jest "multizbiór", więc po co unordered_map, skoro jest w C++ coś takiego jak unordered_multiset? :)

pawel1216 napisał(a):

napiszcie co jest nie tak.

1. Algorytm napisany w main. Brak podziału na funkcje, w związku z czym nie widać gdzie zaczyna się "algorytm" i gdzie kończy. Nie wiadomo jakie ma dane wejściowe a które są tylko pomocnicze. Kod jest przydługi i miesza I/O z algorytmem.

2. Stosujesz jedno-literowe nazwy (co to jest "q"??)

3. Stosujesz zastrzeżone nazwy ("min", "max")

4. Nie sformatowałeś kodu przed publikacją, http://format.krzaq.cc/

5. Stosujesz "magiczne liczby": licznosci[i]=-10;, else if(licznosci[x]!=-10)

6. Stosujesz wielopoziomowe struktury kontrolne: main > blok > if > while > if