DNA soluzione ufficiale fallisce alcuni testcase

Aiuto
1

Altro problema con oii_dna.
Ho implementato la soluzione descritta alla finale di biella facendo 100/100, ma mi sono accorto in locale che può andare ben oltre il limite di 10015 chiamate. Ad esempio con questo input il mio programma fa 10105 chiamate a test:
102 caratteri ‘1’ seguiti da 98 volte la sequenza composta da 100 zeri e un ‘1’.
in python: ‘1’*102+(‘0’*100+‘1’)*98
Non capisco come questo sia possibile, visto che la soluzione prende 100 punti e per quanto riesco a ricordare è proprio quella ufficiale.
Qualcuno sa chiarirmi le idee?

2

Alla riga 24 vuoi controllare se esistono 2 \sqrt N zeri (ricorda di fixare i posti correlati), questo dovrebbe rimuovere le query di troppo.

Edit: prossima volta condividi il codice.

3

Ho aggiornato il codice, ora passa il test in locale ma prende solo 99/100.

Ecco il nuovo codice:

#include <string>
#include <cmath>

using namespace std;

bool test(string T);

int binSearchZeroesAfter(int high, string s) {
    int low = 0, mid;
    while (low+1 != high) {
        mid = (low+high)/2;
        if (test(s + string(mid, '0'))) {
            low = mid;
        } else {
            high = mid;
        }
    }
    return low;
}

string analizza(int N) {
    int tworoot = 2*(int)sqrt(N);
    if (test(string(tworoot, '0'))) {
        string s(tworoot, '0');
        int zeroes;
        do {
            zeroes = 0;
            do {
                if (test(s + '1')) {
                    s += '1';
                    zeroes = 0;
                } else {
                    zeroes++;
                    s += '0';
                }
            } while (zeroes < tworoot && s.length() < N);
        } while (test(s));
        s.resize(s.length() - zeroes + binSearchZeroesAfter(zeroes+1, s.substr(0, s.length() - zeroes)));
        while (s.length() < N) {
            s = test('1'+s) ? '1'+s : '0'+s;
        }
        return s;
    } else {
        int maxZeroes = binSearchZeroesAfter(tworoot, "");
        string s(maxZeroes, '0');
        int zeroes = 0;
        do {
            if (test(s + '1')) {
                s += '1';
                zeroes = 0;
            } else {
                zeroes++;
                s += '0';
            }
        } while (zeroes <= maxZeroes && s.length() < N);
        s.resize(s.length() - zeroes + binSearchZeroesAfter(zeroes+1, s.substr(0, s.length() - zeroes)));
        while (s.length() < N) {
            s = test('1'+s) ? '1'+s : '0'+s;
        }
        return s;
    }
}