Aiuto problema ois_23

Sto cercando di risolvere ois_23 e la mia attuale soluzione però non risolve 2 testcase e 3 vanno in timeout. Mi dareste una mano?
Ecco la mia soluzione:
la mia idea era di sortare il vettore e appena trovavo un numero presente nell’array far assumere al vettore sol in posizione dll’originale posizione del numero il valore dell’attuale “soluzione”;
sumDigits ritorna la somma delle cifre del numero convertito;
mentre solve controlla se la somma delle cifre in base 3 e in base 2 sono uguali e nel caso aumenta un contatore( var buffer) e se il numero è presente nel vettore salvare la sua soluzione

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

using namespace std;

vector<pair<int,int>> V;
vector<int> sol;

int sumDigits(int n, int base) 
{  
	int result = 0 ; 
	while (n > 0) { 
		result+= n % base ; 
		n /= base; 
	}
	return result ; 
} 

void solve() 
{
	int buffer=0,count=0;
	for(int i=1;i<=V[V.size()-1].first;i++){
		
		if(sumDigits(i, 2) == sumDigits(i, 3))
			buffer++;
			
		if(V[count].first==i){
			sol[V[count].second]=buffer;
			count++;
		}
	}
} 

int main()
{

//	freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);
	
	int x,T;
	cin>>T;
	V.resize(T);
	sol.resize(T);
	for(int i=0;i<T;i++){
		cin>>x;
		V[i].first=x;
		V[i].second=i;
	}

	sort(V.begin(),V.end());

	solve();

	for(int i=0;i<T;i++){
		cout<<sol[i]<<" ";
	}

	return 0;
}

Qua puoi trovare degli spunti interessanti.

arrivo a fare 65 su cento ma 3 testcase vanno in timeout

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define MAX_BASE_2 16384
#define MAX_BASE_3 19683 
 
unsigned int T, i, k, c, v;
 
using namespace std;
 
vector<unsigned int> base2(MAX_BASE_2+1);
vector<unsigned int> base3(MAX_BASE_3+1);

int solve2(int x); //sommma delle cifre in base 2
 
int solve3(int n, int base) //sommma delle cifre in base 3
{  
	int result = 0 ; 
	while (n > 0) { 
		result+=n % base; 
		n/= base; 
	}
	return result ; 
} 

unsigned int sum(unsigned int n, unsigned int base)
{
    if (base == 2){
    	
        if (n <= MAX_BASE_2){
        	
        	if(base2[n-1]!=0)
            	return base2[n - 1];
            else 
            	return base2[n - 1] = solve2(n);
        }
        
        else{
            if (n % MAX_BASE_2 == 0)
                return sum(n / MAX_BASE_2,2);
 
            return sum(n % MAX_BASE_2,2) + sum(n / MAX_BASE_2,2);
        }
    }
    
    else{
    	
        if (n <= MAX_BASE_3){
        	
            if(base3[n-1]!=0)
            	return base3[n - 1];
            else 
            	return base3[n - 1] = solve3(n,base);
        }
        
        else{
            if (n % MAX_BASE_3 == 0)
                return sum(n / MAX_BASE_3,3);
 
            return sum(n % MAX_BASE_3,3) + sum(n / MAX_BASE_3,3);
        }
    }
}
 
int solve2(int x){
	if(x==1)
		return 1;
		
	if(x&(x-1)==0)
		return 1;
			
	if(x&(x-1)==x-1||x&(x+1)==0)
		return sum(x-1,2)+1;
		
	if(x%2==0)
		return sum(x/2,2);
}

int main()
{
    cin >> T;
 
    vector<unsigned int> input(T);
    vector<unsigned int> keys;
    map<unsigned int, unsigned int> special_numbers;
 
    for (i = 0; i < T; i++)
    {
        cin >> input[i];
 
        if (count(keys.begin(), keys.end(), input[i]) == 0)
            keys.push_back(input[i]);
 
        k = max(k, input[i]);
    }
 
    priority_queue<unsigned int, vector<int>, greater<unsigned int>> pq;
 
    for (auto e : keys)
        pq.push(e);
 
    v = pq.top();
    pq.pop();
 
    for (i = 1; i <= k; i++){
        if (sum(i, 2) == sum(i, 3))
            c++;
        
 
        if (i == v) {
            special_numbers[i] = c;
 
            if (pq.size() > 0) {
                v = pq.top();
                pq.pop();
            }
        }
    }
 
    for (i = 0; i < T; i++)
        cout << special_numbers[input[i]] << " ";

    return 0;
}

Prova a sostituire

if (sum(i, 2) == sum(i, 3))

con

if (__builtin_popcount(i) == sum(i, 3))
1 Mi Piace

si, ho provato anche in altri modi con il bitwise ma comunque va in timeout, semplicemente riuso sum perche nello stesso momento riempio l’array dove tengo conto dei risultati in base 2 e 3

Ho appena submittato il tuo codice con quella modifica e fa 100

ah… ahahha
perche comunque ho provato ad usare quella funzione per popolare l’array
grazie mille xD