Ciao a tutti,
stavo provando a risolvere Fractal Painting ma non riesco a fare più del 70/100 a causa dei timeout.
Poiché è un problema che può produrre output di grandi dimensioni mi è venuto in mente di sottoporre un main che non facesse altro che creare una griglia, di lato N^K, in cui tutti i punti fossero colorati di bianco per vedere quanto lenta fosse questa parte di codice e ho potuto constatare che di fatto solo questa parte è sufficiente per andare in timeout.
E’ normale che la semplice colorazione della griglia sia così lenta da non lasciare il tempo per eseguire il resto dell’algoritmo?
Una squadra russa è riuscita a risolverla in gara ottenendo 100/100 con le stesse assunzioni, ma anche qualche squadra italiana ha fatto 90 durante la gara 
.
1 Mi Piace
So che alcuni hanno fatto di più di me ma quello che non mi spiego è come mai il codice qui sotto riesce ad andare in TLE.
#include <bits/stdc++.h>
using namespace std;
#define MAXN 10
constexpr int max_pow = 17000;
bool model[MAXN][MAXN];
bool mat[max_pow][max_pow];
int N, K;
int main() {
char line[MAXN+1];
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
scanf("%d %d", &N, &K);
int sum = 0;
int N_K = pow(N,K);
bool* mat_ij;
for(int i {}; i!=N_K; ++i)
{
mat_ij = mat[i];
for(int j {}; j != N_K; ++j)
printf("%c", (*mat_ij++? '.' : '*'));
printf("\n");
}
return 0;
}
Ho levato addirittura la parte che colora di bianco la tabella ma resta comunque troppo lento.
E’ possibile che questo bizzarro risultato sia dovuto alle differenza tra il server di gara e quello che abbiamo a disposizione qui per gli allenamenti?
Non riesco proprio a capire come possa essere possibile, a meno che non ci siano tecniche di fast I/O di cui non conosco gli effetti come usare/non usare i buffer dei flussi di I/O come avviene normalmente.
Ho fatto una cosa simile alla tua: https://pastebin.com/Na1NnWD1
utilizzando fastin e fastout (getchar_unlocked e putchar_unlocked), allo stesso modo ottengo due casi con TLE, e ancora non ho scritto l’algoritmo, ma solo lettura e scrittura dei dati, deve per forza esserci qualcosa che non va
E con fast i/o ottengo 80
Per caso sai se mettere ogni riga in output in un colpo solo trattandola come una stringa sia più veloce?
P.S.:
le funzioni getchar_unlocked() e putchar_unlocked© come funzionano?
Ora sto provando a creare una stringa lunga tutta la matrice e a stamparla in blocco, sembra leggermente più veloce. Per quelle funzioni guarda Fast I/O qui sul forum
Ok grazie, quel “sembra” indica che vai più in timeout?
Che ci vado ancora, ma di meno. Nulla vieta che però in realtà sia solo cambiata la situazione del server
Hai usato le stringhe per il 100/100?
1 Mi Piace
Ti stai basando sul tempo di esecuzione visualizzato nei dettagli della sottoposizione?
L’esecuzione del processo sul server viene terminata appena supera il limite di tempo, quindi il valore “tempo” visualizzato nella tabella, in caso di timeout, non ti permette di capire di quanto hai superato il limite.
Per esempio, se mandi una soluzione con un ciclo while come questo, il tempo di esecuzione indicato rimane sempre poco superiore a 1 secondo, mentre in realtà l’esecuzione non dovrebbe mai terminare
int main() {
while(1==1) {
}
}
Ciao a tutti, stavo facendo cose strane per provare a risolvere Decimal Fractions (ovvero provare a stampare una serie di stringhe in stile C) e mi è comparso per la prima volta da quando sono sul forum il seguente errore: “Execution timed out (wall clock limit exceeded)”.
La cosa che non capisco è che dovrebbe stare a significare che sono andato fuori tempo massimo di esecuzione (ovvero 1 secondo) quando in realtà l’esecuzione in un caso dura meno di 0,7 secondi mentre nell’altro dura meno di 0,8.
Qualcuno gentilmente potrebbe spiegarmi che significa?
Qui viene spiegato quando compare quell’errore: https://forum.digit.cms.di.unipi.it/t/execution-timed-out-wall-clock-limit-exceeded/1677/2
Lo so ottenevo infatti 5/10 pti in più
Grazie mille, quindi nei dettagli delle sottoposizioni vengono mostrati solamente i secondi in cui il server ha eseguito le istruzioni del mio codice e non quelli in cui ha eseguito istruzioni sue per I/O?
Mi puoi rivelare come hai fatto a guadagnare tempo?
Io adesso sono bloccato a 95/100.
@wil93 che dici di aumentare il TL? Rivalutare non credo sia fattibile (700+ submission).
CC @harniver
Io non ho niente in contrario ad aumentare il TL! Mi ricordo che avevamo faticato a tararlo, quindi ci sta che ora possano anche essere un po’ sballati.
TL aumentato a 1.5s 
le vecchie submission non verranno aggiornate, dovete rinviare 
