[Mesh89]

Originariamente inviato da rеpne scasb

La complessita' dovrebbe essere 1*r, ossia non dipende da Find, o meglio dipende pochissimo da f. Ad esempio, nei nuovi due file se invece di aumentare per 10 sia le estrazioni totali che Find, avessi aumentato di 100 volte solo find, il tuo algoritmo avrebbe fatto ugualmente 125 secondi, il mio sarebbe rimasto fermo a 0.2 secondi.

Un altra osservazione: il mio algoritmo e' praticamente indipendente (o meglio leggermente dipendente), da "valori", ossia dai numero degli estratti che nel nostro caso e' 6. Se i valori fossero stati 7,8,9, e il numero dei valori da testare 3,4,5,6,7 non ci sarebbero state praticamente differenze sui tempi misurati*.

* Non e' propriamente cosi', ma nel nostro caso, operando con piccole quantita' di dati, e praticamente vero.

Wow... Mi sembra abbastanza incredibile che non dipenda dal numero di find, a contest finito sarebbe carina una spiegazioncina
Ho buttato giù di un po' i tempi, anche se non dovrei arrivare nemmeno vicino a repne

#include <iostream>
#include <bitset>
#include <string>
#include <vector>
#include <ctime>

using namespace std;


struct Ruota {
	bitset<96> bitmask;
	string* data,* luogo;
	char* numeri;
};
vector<Ruota> ruote;
vector<int> indexed[91];
int lens[91];


int main() {
	FILE* fin = fopen("fin.txt", "r");
	FILE* rin = fopen("rin.txt", "r");
	FILE* out = fopen("out.out", "w");
	int r, v, f, daCercare[9], index=0;
	char s[100];
	clock_t start = clock();

	fscanf(rin, "%s %d\n", s, &r);
	fscanf(rin, "%s %d\n", s, &v);
	fscanf(fin, "%s %d\n", s, &f);

	//Lettura ruote
	ruote.reserve(100010);
	lens[0] = 2000000000;
	while (!feof(rin)) {
		Ruota ruota; int n;
		ruota.numeri = new char[v];
		
		fscanf(rin, "%s", s);
		ruota.data = new string(s);
		fscanf(rin, "%s", s);
		ruota.luogo = new string(s);
		
		for (int i = 0; i < v-1; i++) {
			fscanf(rin, "%d,", &n);
			ruota.bitmask[n] = 1;
			ruota.numeri[i] = (char)n;
			
			indexed[n].push_back(index);
		} fscanf(rin, "%d\n", &n);
		ruota.bitmask[n] = 1;
		ruota.numeri[v-1] = (char)n;
		
		indexed[n].push_back(index);
		
		ruote.push_back(ruota);
		index++;
	}
	for (int i = 1; i <= 90; i++)
	   lens[i] = indexed[i].size();
	   
	cout << "Lettura input: " << (clock()-start)/1000.0 << " secondi" << endl;
	start = clock();
	
	//Risoluzione
	for (int i = 0; i < f; i++) {
		int k = 1, luckyNumber = 0;
		char c;
	
		//Lettura find
		fscanf(fin, "%d", daCercare);
		while (true) {
			fscanf(fin, "%c", &c);
			
			if (c == ',') {
				fscanf(fin, "%d", daCercare+k);
				if (lens[luckyNumber] > lens[daCercare[k]])
				    luckyNumber = daCercare[k];
				k++;
			}
			else break;
		}

		//Ricerca delle ruote vincenti
		bool first = true;
		for (int j = 0; j < lens[luckyNumber]; j++) {
            int n = indexed[luckyNumber][j];
            
			bool OK = true;
			for (int h = 0; h < k; h++) {
				if (!ruote[n].bitmask[daCercare[h]]) {
					OK = false; break;
				}
            }

			if (first && OK) {
				fprintf(out, "-- ");
				for (int h = 0; h < k-1; h++)
					fprintf(out, "%d,", daCercare[h]);
				fprintf(out, "%d --\n", daCercare[k-1]);
				
				first = false;
			}
			if (OK) {
				fprintf(out, "%s %s ", ruote[n].data->c_str(), ruote[n].luogo->c_str());
				for (int h = 0; h < v-1; h++)
					fprintf(out, "%d,", ruote[n].numeri[h]);
				fprintf(out, "%d\n", ruote[n].numeri[v-1]);
			}
		}
	}
	
	cout << "Tempo per la ricerca: " << (clock()-start)/1000.0 << " secondi" << endl;
}