Come posso velocizzare crossover?

Aiuto
1

Ho scritto il codice e ho preso 60/100. Per poco avrei preso 100/100, se non fosse stato per quei 0.100 secondi di velocità in più in 3 testcase di 3 subtask diverse.
Il codice:

#include <iostream>
#include <fstream>
#include <algorithm>
#include <string.h>

using namespace std;

string prima, seconda;
string a, b;

int n_prima, n_seconda;

int main()
{
	ifstream in("input.txt");
	ofstream out("output.txt");
	
	in >> prima >> seconda;

	n_prima = prima.size() - 1;
	n_seconda = seconda.size() - 1;
	
	while(true)
	{		
		if(n_prima == -1  || n_seconda == -1 || prima[0] == '\0' || seconda[n_seconda] == '\0')
			break;
		if(prima[0] == seconda[n_seconda])
		{
			prima.erase(0,1);
			seconda.erase(n_seconda,n_seconda+1);
			
			n_prima--;
			n_seconda--;
			
			swap(prima,seconda);
			swap(n_prima,n_seconda);
		}
		else if(prima[0] != seconda[n_seconda])
		{
			a += seconda[n_seconda];
			
			string temp;
			temp += prima[0];	
			temp += b;
			b = temp;
		
			// elimino i caratteri
			prima.erase(0,1);
			seconda.erase(n_seconda,n_seconda+1);
			
			n_prima--;
			n_seconda--;	
		}
	}
	cout << a << prima << seconda << b;	
}
2

Sicuramente anziché usare una stringa potresti utilizzare un array di char gestendo manualmente gli indici di inizio e fine :slight_smile:

3

Grazie. Ho fatto ciò che mi hai detto e adesso ho preso 90/100.
Mi manca un testcase dove sempre e comunque vado fuori tempo e di tanto.

Questo è il nuovo codice:

#include <stdio.h>
#include <assert.h>
#include <vector>
#include <iostream>
#include <string.h>
#include <math.h>
#include <algorithm>

#define MAXL 100008

using namespace std;

void crossover(char s[], char t[], char result[]) 
{
	int t_inizio = 0;
	int t_fine = strlen(t)-1;
	
	int s_inizio = 0;
	int s_fine = strlen(s)-1;
	
	int t_lung = strlen(t)-1;
	int s_lung = strlen(s)-1;
	
	bool contrario = false;
	
	string a, b;
	
	while(true)
	{
		if(contrario == false)
		{
			if(s_inizio > s_fine || t_inizio > t_fine )
				break;
			if(s[s_inizio] == t[t_fine])
			{
				s_inizio++;
				t_fine--;
				contrario = true;
			}
			else if(s[s_inizio] != t[t_fine] && s[s_inizio] != '\0' && t[t_fine] != '\0')
			{
				a += t[t_fine];
				
				string c = "";
				c += s[s_inizio];
				c += b;
				b = c;
				
				s_inizio++;
				t_fine--;
			}
			else
				break;
		}
		else
		{
			if(s_inizio > s_fine || t_inizio > t_fine )
				break;
			if(s[s_fine] == t[t_inizio])
			{
				t_inizio++;
				s_fine--;
				contrario = false;
			}
			else if(s[s_fine] != t[t_inizio] && s[s_fine] != '\0' && t[t_inizio] != '\0')
			{
				a += s[s_fine];
				
				string c = "";
				c += t[t_inizio];
				c += b;
				b = c;
				
				t_inizio++;
				s_fine--;
			}
			else
				break;
		}
	}
		
	cout << a;
	if(contrario == false)
	{
		for(int i = s_inizio; i <= s_fine; i++)
			cout << s[i];
		for(int i = t_inizio; i <= t_fine; i++)
			cout << t[i];
	}
	else
	{
		for(int i = t_inizio; i <= t_fine; i++)
			cout << t[i];
		for(int i = s_inizio; i <= s_fine; i++)
			cout << s[i];
	}
	
	cout << b;
}


char s[MAXL];
char t[MAXL];
char r[2*MAXL];

int main() 
{
    FILE *fr, *fw;

    fr = fopen("input.txt", "r");
    fw = fopen("output.txt", "w");
    fscanf(fr, "%s %s", s, t);

    crossover(s, t, r);
    fclose(fr);
    fclose(fw);
    return 0;
}
4

Temo possa essere inefficiente il modo in cui concateni le stringhe a e b !
Prova a gestirli come array di char, magari dandogli tu una dimensione prefissata :slight_smile:

5

Finalmente 100/100. Grazie :slight_smile: