Cabala 70/100, TLE

Aiuto
1

La soluzione produce l’output giusto ma va in tle, aiuto?

#include <bits/stdc++.h>
using namespace std;

void occulta(int N, int M, set<long long>& result, long long current, int lastDigit = 0) {

    if (N == 0) {
        result.emplace(current % M);
        return;
    }
        
    result.emplace(current % M);
        
    if (lastDigit != 3) {
        occulta(N - 1, M, result, current * 10 + 3, 3);
    }

    if (lastDigit != 6) {
        occulta(N - 1, M, result, current * 10 + 6, 6);
    }
    
    if (lastDigit != 9) {
        occulta(N - 1, M, result, current * 10 + 9, 9);
    }
}

int main() {

    std::ios::sync_with_stdio(false);
    cin.tie(0);

    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int T;
    cin >> T;

    for(int i = 0; i != T; i++){
        int N, M;
        cin >> N >> M;
        
        set<long long>nums;
        long long current;
        
        occulta(N, M, nums, current);

        cout << *nums.rbegin() << " ";
    }
}
2

Ciao, ho provato il tuo codice e credo che il problema sia che utilizzi un set e la funzione emplace che dovrebbe avere complessità O(log N).
Per evitare questo problema basta usare una variabile dove salvi il massimo che hai trovato e incrementarla quando current%M è maggiore di essa.
Spero di essere stato d’aiuto.

3

Sì, il problema è effettivamente il fattore dovuto alla complessità della funzione emplace. Questo risulta particolarmente evidente se evidenziamo che la dimensione del set può raggiungere 3\cdot 2^{N-1} = \frac{3}{2}2^N=\mathcal{O}(2^N). Allora gli inserimenti nel set hanno complessità \mathcal{O}(\log 2^N) = \mathcal{O}(N), peggiorando la complessità complessiva a \mathcal{O}(T\cdot 2^N\cdot N).
In realtà questa soluzione è comunque molto prossima a passare: usando una priority queue al posto del set (che ha la stessa complessità per gli inserimenti ma con un fattore costante apprezzabilmente migliore) fa 100/100 in circa 200 ms.

4

Grazie mille, una piccolezza che nella fretta non avevo considerato

5

Questa mi mancava, grazie mille del consiglio