10537 2024. 04. 04 18:25:40 Gervid Hadjárat cpp17 Hibás válasz 48/100 185ms 26464 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 Összpont Teszt Verdikt Idő Memória
base 48/100
1 Elfogadva 0/0 3ms 2020 KiB
2 Hibás válasz 0/0 82ms 9496 KiB
3 Részben helyes 2/4 3ms 3152 KiB
4 Részben helyes 2/4 3ms 3256 KiB
5 Részben helyes 2/4 3ms 3412 KiB
6 Részben helyes 2/4 3ms 3508 KiB
7 Részben helyes 2/4 3ms 3636 KiB
8 Hibás válasz 0/4 3ms 3868 KiB
9 Részben helyes 2/4 3ms 4200 KiB
10 Részben helyes 2/4 4ms 4348 KiB
11 Részben helyes 2/4 8ms 5168 KiB
12 Részben helyes 2/4 14ms 5864 KiB
13 Részben helyes 3/6 14ms 6068 KiB
14 Részben helyes 3/6 29ms 7716 KiB
15 Részben helyes 3/6 46ms 9432 KiB
16 Részben helyes 3/6 82ms 12584 KiB
17 Részben helyes 3/6 108ms 14960 KiB
18 Részben helyes 3/6 119ms 17284 KiB
19 Részben helyes 3/6 140ms 19480 KiB
20 Részben helyes 3/6 185ms 23716 KiB
21 Részben helyes 3/6 180ms 25072 KiB
22 Részben helyes 3/6 180ms 26464 KiB