105372024-04-04 18:25:40GervidHadjáratcpp17Hibás válasz 48/100185ms26464 KiB
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <limits.h>
#include <algorithm>
#include <math.h>

using namespace std;

int main()
{
	iostream::sync_with_stdio(0);
	cin.tie(0);

	int n, i, gold, slave;
	cin >> n >> gold >> slave;

	vector<set<pair<int, int>>> cantgotogethere = { { {0, 0} }, { {gold, slave} } };
	map<pair<int, int>, int> citys;
	citys[{ gold, slave }] = 0;

	for (i = 1; i < n; i++)
	{
		cin >> gold >> slave;
		citys[{gold, slave}] = i;

		int left = 1, right = cantgotogethere.size() - 1, m;
		
		while (left < right)
		{
			m = (right + left) >> 1;

			auto pointer = cantgotogethere[m].lower_bound({ gold, slave });

			if (pointer != cantgotogethere[m].begin() && prev(pointer).operator*().second < slave && prev(pointer).operator*().first < gold)
			{
				left = m + 1;
			}
			else
			{
				right = m;
			}
		} 
		
		auto pointer = cantgotogethere[left].lower_bound({ gold, slave });

		if (pointer != cantgotogethere[left].begin() && prev(pointer).operator*().second < slave && prev(pointer).operator*().first < gold)
		{
			cantgotogethere.push_back({ {gold, slave} });
		}
		else
		{
			while (pointer != cantgotogethere[left].end() && pointer.operator*().second > slave)
			{
				cantgotogethere[left].erase(*pointer);
				pointer = cantgotogethere[left].lower_bound({ gold, slave });
			}
			cantgotogethere[left].insert({ gold, slave });
		}
	}

	cout << cantgotogethere.size() - 1 << '\n';

	vector<int> out;
	out.reserve(cantgotogethere.size());

	pair<int, int> last = *cantgotogethere.back().begin();

	out.push_back(citys[{gold, slave}]);

	i = cantgotogethere.size() - 2;

	while (i > 0)
	{
		auto pointer = prev(cantgotogethere[i].lower_bound(last));
		out.push_back(citys[*pointer]);
		last = *pointer;
		i--;
	}

	for (i = out.size()-1; i > -1; i--)
	{
		cout << out[i] + 1 << ' ';
	}
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base48/100
1Elfogadva0/03ms2020 KiB
2Hibás válasz0/082ms9496 KiB
3Részben helyes2/43ms3152 KiB
4Részben helyes2/43ms3256 KiB
5Részben helyes2/43ms3412 KiB
6Részben helyes2/43ms3508 KiB
7Részben helyes2/43ms3636 KiB
8Hibás válasz0/43ms3868 KiB
9Részben helyes2/43ms4200 KiB
10Részben helyes2/44ms4348 KiB
11Részben helyes2/48ms5168 KiB
12Részben helyes2/414ms5864 KiB
13Részben helyes3/614ms6068 KiB
14Részben helyes3/629ms7716 KiB
15Részben helyes3/646ms9432 KiB
16Részben helyes3/682ms12584 KiB
17Részben helyes3/6108ms14960 KiB
18Részben helyes3/6119ms17284 KiB
19Részben helyes3/6140ms19480 KiB
20Részben helyes3/6185ms23716 KiB
21Részben helyes3/6180ms25072 KiB
22Részben helyes3/6180ms26464 KiB