Софтуерно Инженерство
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