Błąd masz w funkcji liczenia ile jest punktów kratowych wewnątrz okręgu o danym promieniu. Wkleiłem mój kod liczący tą funkcję i wchodzi na 100pkt. Co ciekawe, po napisaniu swojej funkcji do tego popatrzyłem na twoją i jest praktycznie bliźniacza, tylko twój błąd jest taki, że zmienne x oraz R są intem, a robisz x*x i potem R*R i Ci się wywala z int-a - WA. Wystraczy, że z int-a zmienisz na long long-a i masz 100pkt. Trzeba uważać na przepełnienia int-ów, np. częstą pomyłką jest to jak liczysz iloczyn wektorowy. Kiedyś byłem na warsztatach algorytmicznych na UJ i wykładowca mówił, że drużyna UJ kilka lat temu przez to, że nie dała long-longów tylko int-y przy liczeniu iloczynu wektorowego straciła medal na jakieś międzynarodowej olimpiadzie studentów czy czymś takim.
Teraz kilka rzeczy
Po pierwsze w linii 10 piszesz: ll m, a potem w funkcji do bin searcha przekazujesz m.(To nie psuje chyba, ale po co, prosisz się o kłopoty!)
Po co w pętli w 14 lini napisałeś long long i, skoro masz typedef ll i wcześniej piszesz ll?(nie mówię, że jest to błąd, ale po co)
Ostatnia rzecz jest taka, że paskudnie piszesz binary searcha. Moim zdaniem ładniej pisząc bin searcha środek liczyć w środku pętli, a nie przed i zwracać początek / koniec (zależy od przypadku), ale ogólnie mój sposób jest taki: jak chcę znaleźć najmniejszy pasujący, to kod do bin searcha wygląda tak:
int poczatek = 0, koniec = 1e6+1, srodek = 0;
while(koniec - poczatek > 1)
{
srodek = (poczatek + koniec) / 2;
if (ile_punktow_kratowych(srodek) >= m)
koniec = srodek;
else
poczatek = srodek;
}
return koniec;
Idea jest taka, że jak chcesz znaleźć liczby w przedziale [1,N], to początek ustawiasz na 0, koniec na N+1, możesz zastanawiać się dlaczego na 0 i N+1, zamiast 1 i N? Odpowiedź jest prosta. Jeżeli chcę zwracać koniec i odpowiednią odpowiedzia jest koniec = 1, a dam początek = 1, to koniec nigdy tam nie dojdzie - WA, analogicznie z początkiem na N. Oczywiście można to if-ować jak ty, ale po co. Musisz być tylko uważny, kiedy zwracasz początek kiedy koniec - w zależności czy chcesz znaleźć pierwszy czy ostatni pasujący, oraz, żeby nie przesadzić np. cofając początek o 2 do tyłu, bo przy tablicy może Ci indeks spać z [0,n-1], ale jak dasz jeden wcześniej początek, i jeden dalej koniec, to środek będzie w przedziale[początek + 1, koniec - 1], więc nie będziesz miał idx-ów poza tablicą, ale jak już dasz, np początek = -3 zamiast -1, to ujemne idx-y i signal możesz dostać. Reasumując: początek jedno wcześniej, koniec jedno dalej, i elo. Możesz zastanowić się, czy taka implementacja bin searcha Ci odpowiada, ja tak piszę ciągle.
Edit: oczywiście zamiast przekazywać zmienną R jako long long-a zamist int-a, możesz przekazać int-a i rzutować w trakcie liczenia R*R na long long-a, w sensie (ll)R * (ll)R, tu to raczej nie ma znaczenia, ale jak przekazujesz dużo zmiennych do funkcji, to przekazanie long long-a może raczej trochę opóźnić czas niż przekazanie int-a.