Loading...
WasteOfRAM avatar WasteOfRAM 5 Точки

04. Ranges

Кода изпълнява задачата но за 0.920 s. Пробвах няколко вариации но нещо не ми се получава. Ако може някои да подскаже коя е бавната част.

void chckIfInRange(const std::vector<std::shared_ptr<std::pair<int, int>>>& ranges, const std::vector<int>& numbersToCheck)
{
	std::string inOrOut;
	for (const int& num : numbersToCheck)
	{
		for (const auto& range : ranges)
		{
			if (num >= range->first && num <= range->second)
			{
				inOrOut = "in";
				break;
			}
			else
			{
				inOrOut = "out";
			}
		}
		std::cout << inOrOut << '\n';
	}
}

int main()
{
	
	std::vector<std::shared_ptr<std::pair<int, int>>> ranges;
	std::shared_ptr<std::pair<int, int>> range;
	int from;
	int to;

	while (std::cin >> from >> to)
	{
		range = std::make_shared<std::pair<int, int>>(from,to);
		ranges.emplace_back(range);
	}

	std::cin.clear();
	std::cin.ignore(1);

	int checkNum;
	std::vector<int> numbersToCheck;

	while (std::cin >> checkNum)
	{
		numbersToCheck.emplace_back(checkNum);
	}


	chckIfInRange(ranges, numbersToCheck);
	

	//system("PAUSE");
 	return 0;
}

 

Тагове:
0
C++ Advanced
Zmyrt avatar Zmyrt 3 Точки

Заформи се клуб  "30/100"  в групата явно. И аз имам същите проблеми със скоростта а вече 4 решения написах. В нито едно от тях не се избягва проверката отнемаща R*N операции ( за всяко число да се обходят всички обхвати ) и ми се струва , че основният проблем е там както каза Мартин . Как точно да го заобиколим обаче не се сещам до момента 

0
Filipbg avatar Filipbg 26 Точки

Добави този include #include <bits/stdc++.h>

https://www.geeksforgeeks.org/fast-io-for-competitive-programming/

Също така добави и този код преди потоците 

    cin.sync_with_stdio(false);
    cout.sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    ostringstream::sync_with_stdio(false);
    istringstream::sync_with_stdio(false);
    ostream::sync_with_stdio(false);
    istream::sync_with_stdio(false);
    cin.tie(NULL);

И ползвай '/n' вместо std::endl при принтирането.

Така се маха сихронизацията на input/output-a и проверките минават доста по-бързо. Особено при 1 000 000 000 проверки.

lower_bound и upper_bound както MartinBG е добавил са нужни за тази задача и помагат доста. 

До вчера и аз си късах нервите с тази задача. И така мина. Разрових се в нета за тези разлики в скоростта и намерих тази статия в която е много добре обяснено: 

https://www.modernescpp.com/index.php/c-core-guidelines-improved-performance-with-iostreams

0
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.