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łkowitaq
(1<=q<=100 000
) oznaczająca liczbę zapytań. W każdym z kolejnychq
wierszy znajduje się jedna liczba całkowitax
(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;
}