Fişierul intrare/ieşire:	binsearch.in, binsearch.out	Sursă	EJOI 2021, ziua 2
Autor	Alexa Tudose	Adăugată de	Voicu Mihai Valeriu •cadmium_
Timp execuţie pe test	0.5 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Binsearch

ATENTIE: La aceasta problema, punctajul maxim va fi considerat 200.

bool binary_search(int n, int p[], int target){
  int left = 1, right = n;
  while(left < right){
    int mid = (left + right) / 2;
    if(p[mid] == target)
      return true;
    else if(p[mid] < target)
      left = mid + 1;
    else
      right = mid - 1;
  }
  if(p[left] == target) return true;
  else return false;
}

Este bine ştiut faptul că dacă p este sortat, atunci codul returnează true dacă şi numai dacă target apare în p. Pe de altă parte, acest lucru poate să nu se întâmple dacă p nu este sortat.

Vi se dă un număr natural n şi o secvenţă b₁,..., b_n ∈ {true, false}. Se garantează că există un număr natural k pentru care n = 2^k − 1. Trebuie să generaţi o permutare p a elementelor {1, . . . , n} care îndeplineşte anumite condiţii. Fie S(p) numărul de indici i ∈ {1,..., n} pentru care binary_search(n, p, i) nu returnează b_i. Trebuie sa alegeţi p astfel încât S(p) este mic (aşa cum este detaliat în secţiunea "Restricţii").

(Notă: a permutare a mulţimii {1, . . . , n} este o secvenţa de n numere naturale care conţine fiecare numar natural de la 1 la n fix odată.)

Date de intrare

Fişierul de intrare binsearch.in conţine pe prima linie T, numărul de teste. Urmează apoi testele.

Prima linie a unui test conţine numărul natural n. Pe cea de-a doua linie se găseşte un şir de n caractere ce conţine doar caracterele '0' şi '1'. Aceste caractere nu sunt separate prin spaţii. Dacă cel de-al i-lea caracter este '1', atunci b_i = true, iar dacă este '0', atunci b_i = false.

Date de ieşire

În fişierul de ieşire binsearch.out se va afla pentru fiecare test câte o linie, ce conţine o permutare p.

Restricţii

• Fie S suma tuturor valorilor n într-un singur fişier.
• 1 ≤ N ≤ 100 000
• 1 ≤ T ≤ 7 000
• Există un număr natural k pentru care n = 2^k − 1
• Dacă S(p) ≤ 1 pentru toate testele dintr-un subtask, atunci se primesc 100% din punctele alocate acelui subtask.
• În caz contrar, dacă 0 ≤ S(p) ≤ k (unde 2^k = n - 1) pentru toate testele dintr-un subtask, atunci se primesc 50% din punctele alocate acelui subtask.
• În plus:

Exemple

Explicaţie

Exemplul 1. În primele două teste avem S(p) = 0.
În cel de-al treilea test, avem S(p) = 1. Acest lucru se întâmplă deoarece binary_search(n, p, 2) returnează true, deşi b₂ = false.
În cel de-al patrulea test, avem S(p) = 1. Acest lucru se întâmplă deoarece binary_search(n, p, 4) returnează true, deşi b₄ = false.

Exemplul 2. Avem S(p) = 0 pentru ambele teste.

Cum se trimit solutii?