Aiuto con ottimizzazione Cestini su Terry

Aiuto
1

Buonpomeriggio, ho trovato una soluzione al problema cestini tramite scrivendo il seguente codice:

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

int main() {
	freopen("cestini_input_1.txt", "r", stdin);
	freopen("cestini_output_1.txt", "w", stdout);
	int T;
	cin>>T;
	for(int t=1; t<=T; t++){
	int N,M, Q;
	cin>>N>>M>>Q;
	string s;
	cin>>s;
	char azione[Q];
	int a, b;
	map<int, string> lamiamap;
	
	lamiamap[0]=s;
	
	cout<<"Case #"<<t<<": ";
	for(int i=0; i<Q; i++){
		cin>>azione[i];
		if(azione[i]=='s'){
			cin>>a>>b;
			if(lamiamap[b].empty()) lamiamap[b]=lamiamap[a].back();
			else lamiamap[b]+=lamiamap[a].back();
			s.pop_back();
			lamiamap[a]=s;	
		}
		else{
			string salva;
			salva=lamiamap[a];
			cout<<salva[b];
		}
	}
	cout<<endl;
}


return 0;
}

Solo che questa soluzione pur avendo una logica giusta, non è di una complessità ottimale siccome non stampa nemmeno un caso. Quindi l’ho ottimizzato in questo modo ma comunque risponde solo ai primi due casi. Cos’altro dovrei modificare?

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

int main() {
    freopen("cestini_input_2.txt", "r", stdin);
    freopen("cestini_output_22.txt", "w", stdout);
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        int N, M, Q;
        cin >> N >> M >> Q;
        
        vector<char> s(N);
        for (int i = 0; i < N; i++) {
            cin >> s[i];
        }

        vector<char> cestini[M];
        cestini[0] = s;

        vector<pair<char, pair<int, int>>> azioni(Q);
        for (int i = 0; i < Q; i++) {
            cin >> azioni[i].first;
            if (azioni[i].first == 's') {
                cin >> azioni[i].second.first >> azioni[i].second.second;
            } else {
                cin >> azioni[i].second.first >> azioni[i].second.second;
            }
        }

        cout << "Case #" << t << ": ";
        for (int i = 0; i < Q; i++) {
            if (azioni[i].first == 's') {
                int a = azioni[i].second.first;
                int b = azioni[i].second.second;
                cestini[b].emplace_back(cestini[a].back());
                cestini[a].pop_back();
            } else {
                int a = azioni[i].second.first;
                int b = azioni[i].second.second;
                cout << cestini[a][b];
            }
        }
        cout << endl;
    }
    return 0;
}
2

Ciao, a me sembra che il tuo codice stampi (anche abbastanza velocemente) il risultato. Una cosa che mi sembra strana è che il codice va in segfault dopo un po’ – ma questo è un altro problema.
Riguardo all’ottimizzazione, i suggerimenti sono pochi:

  • Evita (e questo come linea generale) di includere bits/stdc++.h. Questo riduce la dimensione del file eseguibile di qualche KB. C’è anche un altro motivo per cui non usarlo ma è puramente tecnico e non influisce con la velocitĂ  del codice.
  • All’inizio del main, scrivi questo codice, che velocizza (in una maniera un po’ brutta) l’I/O:
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
  • Andando sulla logica, serve davvero memorizzarsi le azioni da fare?
  • Al posto di usare std::endl usa \n.

In questo modo il codice si velocizza notevolmente. Considera comunque che la mia soluzione da 100 (l’ho anche provata a rifare in Python!) ci mette circa 15s a calcolare l’output – in gara hai 10m per caricare la risposta corretta.

Spero di averti dato una mano :slight_smile:

3

Ciao fabrizio, si stampa molto velocemente ma solo i primi due casi il terzo e gli altri non li stampa proprio come se crashasse. Ho ottimizzato il codice però comunque il problema rimane quello. Ma questo va messo prima di freopen o dopo?

ios::sync_with_stdio(false);
cin.tie(nullptr);
4

Ciao, è esattamente quello che ti dicevo: il codice va in segfault dopo un po’ di testcase. Il “crash” che ti appare è in realtà questo:
image

Riguardo all’ottimizzazione su I/O, va bene messa dovunque ma prima della lettura/scrittura da file effettiva (ovvero prima di cin >> o cout <<).

Se ti interessa la soluzione al segfault, ecco alcuni suggerimenti:

  • Inizializza il vettore cestini una sola volta – anche per l’ottimizzazione (fuori dal main, come vector<char> cestini[MAXM];, con MAXM = 500000 + 1).
  • In ogni caso di test, inizializza s come stringa, poi itera sui caratteri per aggiungerli al vettore all’indice 0.
  • All’inizio di ogni testcase, svuota l’array cestini (un for-loop con estremi [0, MAXM), per ognuno dei quali chiami cestini[i].clear()).

Se ti può essere d’aiuto ti invio la mia soluzione in C++ (che ci mette circa tra gli 0.5 e gli 0.8 secondi per risolvere i casi di test della piattaforma). Buona serata!

1 Mi Piace
5

P.S. non è necessariamente così nei problemi che incontrerai (in questo caso sì). Se ad esempio crei un codice greedy che ci mette un sacco a risolvere un testcase, non è detto che i casi risolti che vedi sul file corrispondono a quelli svolti veramente: il computer si tiene infatti in memoria alcune stringhe da scrivere sul file in modo da effettuare il minor numero di operazioni “scritttura” possibile. Per forzare il processo di inserimento sul file dovresti usare std::cout << std::flush ogni volta che hai bisogno di scrivere immediatamente la stringa che stai mandando a cout (std::endl lo fa automaticamente, ed è per questo che non andrebbe mai usato per
sostituire \n).

6

Grazie mille. Ora fa 10/10 e non impiega nemmeno molto a stampare l’output! Ti auguro una buona gara :grin:.

1 Mi Piace