Comparari

Fie un șir de N numere întregi, indexat de la 1. Numim al doilea maxim al șirului cel mai mare număr din șir, cu excepția maximului. Pentru a afla maximul și al doilea maxim, veți efectua comparări între elementele șirului.

Având la dispoziție numai $N+⌈log_2N⌉-2$ comparări, aflați pozițiile pe care le ocupă maximul și al doilea maxim. Prin $⌈log_2N⌉$ s-a notat partea întreagă superioară a lui „logaritm în baza 2 din N".

Cerință

Aflați cele două numere, efectuând cel mult $N+⌈log_2N⌉-2$ comparări. Pentru a putea efectua comparările, vă este pusă la dispoziție funcția:

int compare(int i, int j)

care compară numarul de pe poziția i cu cel de pe poziția j și vă returnează 1, dacă elementul aflat pe poziția i este mai mare sau egal cu cel de pe poziția j, respectiv -1, în caz contrar. Dacă i sau j nu este un indice valid, atunci funcția va returna 0.

Programul trebuie să implementeze funcția

std::pair<int, int> solve (int N)

unde N are semnificația din enunț. Funcția va returna cele două valori cerute.

Restrictii şi precizări

• 2 ≤ N ≤ 100 000
• Fișierul compare.h trebuie inclus
• Problema a fost modificată
• Pentru 20 de puncte puteți folosi un număr maxim de $2 \cdot N-3$ comparări
• Pentru alte 80 de puncte puteți folosi un număr maxim de $N+⌈log_2N⌉-2$ comparări

Exemplu 1

Dacă șirul considerat este (5, 3, 4), atunci o executare corectă a programului este următoarea:

compare(1, 2) care returnează 1;

compare(1, 3) care returnează 1;

compare(2, 3) care returnează –1;

În acest moment ați epuizat numărul de comparări permise (3+2-2=3 comparări) și funcția va returna numerele 1 si 3, reprezentând pozițiile pe care se află maximul șirului (5), respectiv al doilea maxim (4).

Exemplu 2

Dacă șirul considerat este (5, 7, 7), o executare corectă a programului este următoarea:

compare(1, 2) care returnează -1;

compare(2, 3) care returnează 1;

compare(1, 3) care returnează –1;

În acest moment ați epuizat numărul de comparări permise (3+2-2=3 comparări) și funcția va returna numerele 2 si 3, reprezentând pozițiile pe care se află maximul șirului (7), respectiv al doilea maxim (7).

Observație:
Pentru acest exemplu, mai există o soluție corectă, cea în care considerați maximul (7) pe poziția 3 și al doilea maxim (7) pe poziția 2.