Tecnico Pazzo (tecnico)

Quale tipo di struttura dati potrei applicare per risolvere in tempo logaritmico (o comunque in meno tempo rispetto ad una soluzione lineare) l’esercizio Tecnico Pazzo.

Meno di tempo lineare mi sembra difficile, anche solo per il fatto che l’input lo devi leggere tutto.

1 Mi Piace

Ma la vera domanda è: perchè?

Perchè ho applicato una soluzione lineare e quest’ultima nel caso peggiore, cioè l’ultimo, impiega circa 1 secondo in più del tempo limite. In più l’algoritmo esce nel penultimo testcase.
Il codice è questo:

#include <bits/stdc++.h>

#define MAXN 3000100

using namespace std;
    
int N, M;
int posizioni[MAXN];
int log_pc[MAXN];

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

	cin >> N >> M;

	for(int i = 0; i < N; i++)
	{
		posizioni[i] = i;
		log_pc[i] = i;
	}
	
	for(int i = 0; i < M; i++)
	{
		int primo, secondo;
		cin >> primo >> secondo;

        // prelevo le posizioni attuali dei due computer                         
		int pos_primo = posizioni[primo];
		int pos_secondo = posizioni[secondo];

		swap(log_pc[pos_primo], log_pc[pos_secondo]); 
    	swap(posizioni[secondo], posizioni[primo]);
	}

	cout << log_pc[0] << endl;
	
	return 0;
}

Probabilmente perdo tempo con il primo for assegando la posizione a tutti gli elementi.

Invece di swappare ogni volta perché semplicemente non consideri solo i casi in cui è coinvolto il computer che attualmente si trova alla posizione 0? :wink:

1 Mi Piace

YOU ARE A GENIUS (questa cosa l’avevo già utlizzata per il problema grandprix ma non c’ho pensato)

Oppure puoi semplicemente usare scanf invece di cin :slight_smile:

1 Mi Piace

Sì ma non è ottimale :wink:

1 Mi Piace