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.

Cerința

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

(Notă: o permutare a mulțimii of {1, 2, ..., n} este o secvență de n numere naturale care conține fiecare număr natural de la 1 la n o singură dată.)

Date de intrare

Prima linie a intrării standard conține 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

Răspunsul pentru un test va fi o permutare p.

Restricții și precizări

• Fie ∑n suma tuturor valorilor n dintr-o intrare.
• 1 ≤ sum n ≤ 100.000
• 1 ≤ T ≤ 7.000.
• Există un număr natural k pentru care n = 2k - 1
• Dacă S(p) ≤ 1 pentru toate testele dintr-un subtask, atunci se primesc 100% din punctele alocate acelui subtask.
• În caz contrar, dacă 1 ≤ 2S(p) ≤ n+1 pentru toate testele dintr-un subtask, atunci se primesc 50% din punctele alocate acelui subtask.
• Pentru 3 puncte, b[i] = true
• Pentru 4 puncte, b[i] = false
• Pentru 16 puncte, 1 ≤ n ≤ 7
• Pentru 25 puncte, 1 ≤ n ≤ 15
• Pentru 22 puncte, n = 216 - 1 și fiecare b[i] este generat uniform aleator din mulțimea {true, false}
• Pentru 30 puncte, fără restricții suplimentare

Exemplul 1:

Intrare

4
3
111
7
1111111
3
000
7
000000000

Ieșire

1 2 3
1 2 3 4 5 6 7
3 2 1
7 6 5 4 3 2 1

Explicație

Î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[2] = 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[4] = false.

Exemplul 2:

Intrare

2
3
010
7
0010110

Ieșire

3 2 1
7 3 1 5 2 4 6

Explicație

Avem S(p) = 0 pentru ambele teste.