Aiuto enigmath TLE


#1

è da un po’ che sto provando a risolvere il problema enigmath solo che non riesco ad ottenere più di 80 punti

 #pragma GCC compiler("O3")
#include <bits/stdc++.h>
using namespace std;
int p[1002000];
int somma(int num){
    int a=0,tot=num%10,s=num;
    while(num>9){
      num/=10;
      tot+=num%10;
    }
    if(tot>9){
        a=tot/10+tot%10;
        tot+=a;
    }
    if(a>9)tot+=a%10+a/10;
    tot+=s;
    return tot;
}
int main(){
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    ios_base::sync_with_stdio(false);
    int mi,ma;
    cin>>mi>>ma;
    if(mi==0){
        cout<<0<<endl;
        mi++;
    }
    for(int i=max(mi-110,1);i<=ma;i++){
        if(i<10){
            p[i-mi+200]=i;
            continue;
        }
        int o=somma(i);
        if(p[o-mi+200]>0)p[o-mi+200]=1000000009;
        else p[o-mi+200]=i;
    }
    for(int i=mi;i<=ma;i++){
        if(p[i-mi+200]==0)cout<<"IMPOSSIBLE"<<endl;
        else if(p[i-mi+200]==1000000009)cout<<"AMBIGUOUS"<<endl;
        else cout<<p[i-mi+200]<<endl;
    }
    return 0;
}

Per ogni valore i compreso tra Emin-110 e Emax calcolo il suo valore K dopo essere stato criptato e in un array in posizione K assegno i se la casella era vuota o 1000000009 se vi era già un valore (e quindi la risposta sarà AMBIGUOUS).
alla fine per ogni casella stampo a risposta in base al valore che contiene (IMPOSSIBLE se è 0, AMBIGUOUS se è 100000000009, o il valore altrimenti).
Se non mi sbaglio la complessità dovrebbe essere O((Emax-Emin)*G), dove G è il numero di cifre del valore, dato che (Emax-Emin) è al massimo 1e6 e G è al massimo 9, non riesco a capire come possa andare int TLE. Qualcuno potrebbe aiutarmi? Grazie.


#2

In realtà nella complessità vi è un fattore \log^*(E_{max}) che non consideri (\log^* è il logaritmo iterato), per fare 100 devi rimuovere quel fattore.


#3

Scusa ma non ho capito bene che cos’è il logaritmo iterato e in quale parte del codice è presente.
EDIT: Guardando meglio ho capito il punto del codice in cui è presente, solo che se ho capito bene riguarda solo le 3 operazioni della funzione somma, e non capisco come possa rallentare di così tanto il programma dato che il while lo avevo già considerato nella complessità e le altre due operazioni sono dei semplici if…
Non so se sono riuscito a spiegarmi


#4

Questo che poi è sempre il tuo fa 100

#define _CRT_SECURE_NO_WARNINGS
#include
#pragma GCC compiler(“O3”)
//#include <bits/stdc++.h>
using namespace std;
#include <stdio.h>
int p[1002000];
int somma(int num){
int a=0,tot=num%10,s=num;
while(num>9){
num/=10;
tot+=num%10;
}
if(tot>9){
a=tot/10+tot%10;
tot+=a;
}
if(a>9)tot+=a%10+a/10;
tot+=s;
return tot;
}
int main(){
freopen(“input.txt”,“r”,stdin);
freopen(“output.txt”,“w”,stdout);
//ios_base::sync_with_stdio(false);
int mi,ma;
scanf("%d%d",&mi,&ma);
//cin>>mi>>ma;
if(mi==0){
//cout<<0<<endl;
printf(“0\n”);
mi++;
}
for(int i=max(mi-110,1);i<=ma;i++){
if(i<10){
p[i-mi+200]=i;
continue;
}
int o=somma(i);
if(p[o-mi+200]>0)p[o-mi+200]=1000000009;
else p[o-mi+200]=i;
}
for(int i=mi;i<=ma;i++){
if(p[i-mi+200]==0)
printf(“IMPOSSIBLE\n”);
else
if(p[i-mi+200]==1000000009)
printf(“AMBIGUOUS\n”);
else
printf("%d\n",p[i-mi+200]);
}
return 0;
}

la #include vuota è in realtà #include algorithm>
In sostanza ho tolto cin e cout (le funzioni di I/O più lumache del panorama c/c++ e le ho sostituite con le più decenti scanf e printf e si può fare di meglio.
Cin e similari vanno benissimo se non devi leggere più di 10 dati e qui potevano andare.
Cout e similari vanno bene per stampare un risultato poi lasciale a casa!
P.S. questa versione gira in circa 330ms.


#5

Hai ragione in realtà non cambia molto, però è un buon accorgimento da fare. Ciò che forse velocizza molto il codice è sostituire “endl” con “'\n'”.


#6

Si può fare 100 benissimo anche solo con cin/cout senza neanche usare sync_with_stdio. Inoltre non direi che scanf/printf siano migliori, già solo per il fatto che devi definire la macro _CRT_SECURE_NO_WARNINGS.


#7

Ciao, non avevo mai sentito dire che /n fosse più veloce di endl, esiste un motivo particolare?
Grazie mille ad entrambi


#8

endl fa un “flush” dell’output che se eseguito molte molte rallenta il programma, invece stampando solo \n l’output viene bufferizzato.


#9

Quella #define è una pignoleria del mio compilatore microsoft perchè da un punto di vista professionale fopen, scanf , printf etc non sono sicure e se uno le vuole proprio usare deve mettere quella define, ma tranquilli che la potete tranquillamente togliere e in ambiente non windows gira perfettamente e velocemente. Se nei problemi col grader.cpp che si scarica l’input/output viene fatto con scanf e printf e non con cin e cout un motivo ci sarà


#10

Per quanto riguarda input/output aggiungere cin/cout.tie(0) riesce ad avvicinarli a scanf/print?
Ho notato che se si risolvono query mentre le si prendono in input ottimizzano molto


#11

Per esser precisi:
_CRT_SECURE_NO_WARNINGS .
non è una macro.


#12

Il grader viene preparato sia per il C che per il C++ e per non scrivere due grader diversi vengono usate scanf/printf (siccome nel C non sono presenti cin/cout). Inoltre quella define serve a ignorare i warning del compilatore ed ignorare i warning non è mai una buona cosa.


#13

Solo usare ios::sync_with_stdio(false) rende scanf/printf e cin/cout veloci uguale.


#14

Se non erro allora cout.tie(0) dovrebbe sistemare il problema del flush


#15

Il compilatore microsoft di visual studio senza quella #define non da un warning non compila proprio mentre tutti gli altri compilatori compreso quello usato nel portale non danno neanche un warning!!
Ripeto fate come se non ce l’avessi messo!!