JA1-Task-4-Roxettes
Не знам дали е прието да си поставяме кода тук, ако не е прието обещавам да не правя повече така. Та идеята ми е къде може да се оптимизира кода по-долу защото judge гърми та трещи от 6-ти тест нататък за време и на последния за памет.
#include <iostream>
#include <vector>
#include <sstream>
using namespace std;
int main() {
string dnaSequence {};
vector<short int> dnas;
unsigned short int pos;
cin >> dnaSequence;
unsigned int length = dnaSequence.length();
if (length > 15) {
string currDna{};
for (int i = 0; i <= length; i++) {
if (i % 5 == 0 && i > 0) {
short int x = stoul(currDna, nullptr, 16);
dnas.push_back(x);
currDna = {};
}
currDna = currDna + dnaSequence[i];
}
unsigned int numDna = (length - 1)/5;
for (int i = 0; i < numDna; i++) {
bool isUnique{true};
for (int j = 0; j < numDna; j++) {
if (i != j && dnas[i] == dnas[j]) {
isUnique = false;
break;
}
}
if (isUnique == true) {
pos = i;
break;
}
}
for (int i = pos * 5; i <= pos * 5 + 4; i++) {
cout << dnaSequence[i];
}
}
else if (dnaSequence.length() == 6){
cout << dnaSequence << endl;
}
return 0;
}
Здравей Георги.
В предишния курс задачата ме изяде, тогава не успях да взема 100те точки точно поради 2та мегабайта ограничение.В момента си мисля, ако използвам двумерен масив от чарове в които една Роксет ДНК ще бъде 5бита, ще ми позволи ли да се вмъкна във времето и 2MB памет?
Здравей,
В паметта може и да се вмъкнеш (както е настроена сега за 16 МБ, вместо 2-та които пише в условието), но във времето почти със сигурност няма да се вмъкнеш само с масив - търсенето ще ти отнема твърде много време. set би бил по-добър вариант (търсенето е много по-бързо).
При всички положения това, което обясних на лекцията, е доста по-бързо и ефикасно от всички други подходи, които се мъчат да пазят самите елементи.
Поздрави,
Жоро
Задачата наистина е много добра! :)
В предишното издание на курса успях да се вмъкна в изискването за памет като ползвах bitset (това решение може да се приложи за произволен брой уникални ентрита), но правилното решение е друго (hint - побитови операции).