113572024-08-23 08:54:58GervidHadjáratcpp17Elfogadva 100/100125ms1156 KiB
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <limits.h>
#include <algorithm>
#include <math.h>
#include <fstream>

using namespace std;

struct City
{
	int slaves, gold, index;

	bool operator<(const City other) const
	{
		return slaves < other.slaves;
	}

	bool operator==(const City other) const
	{
		return slaves == other.slaves;
	}
};

vector<set<City>> stairs = { { { -1, -1, -1 } } };
vector<int> last;

int fits_on_top(int index, City& city)
{
	auto it = stairs[index].lower_bound(city); //(get strictly smaller step by slaves) <- prev()!!!

	if (it == stairs[index].begin()) return -2; //if it doesn't exists, the city won't fit on top
	
	if (prev(it).operator*().gold < city.gold) return (*prev(it)).index; //if the step is smaller in gold too, the city fits on top of it
	else return -2;
}

void del(int index, City& city)
{
	auto it = stairs[index].lower_bound(city);
	while (it != stairs[index].end() && city.gold <= it.operator*().gold)
	{
		stairs[index].erase(*it);
		it = stairs[index].lower_bound(city);
	}
}

void insert_to_stair(int index, City& city)
{
	auto before = stairs[index].upper_bound(city); //(get smaller or equal step by slaves) <- prev()!!!

	if (before == stairs[index].begin()) //if the city has the least slaves
	{
		del(index, city);
		stairs[index].insert(city);
		return;
	}
	before = prev(before);

	auto after = stairs[index].lower_bound(city); //get bigger or equal step by slaves

	if (after == stairs[index].end()) //if the city has the most slaves
	{
		if (city.gold < prev(stairs[index].end()).operator*().gold)
		{
			stairs[index].insert(city);
		}
		return;
	}

	if (after == before) //if step is equal by slaves
	{
		if (city.slaves < after.operator*().gold)
		{
			del(index, city);
			stairs[index].insert(city);
		}
		return;
	}

	if (city.slaves == max(after.operator*().slaves, before.operator*().slaves) || city.gold == max(after.operator*().gold, before.operator*().gold))
	{
		return;
	}

	del(index, city);
	stairs[index].insert(city);
}

void process(City city)
{
	//binary search for the right stair
	int l = 0, r = stairs.size() - 1, m = 0;
	
	while (l < r)
	{
		m = (l + r) / 2;

		int returned = fits_on_top(m, city);

		if (returned != -2)
		{
			last[city.index] = returned;
			l = m + 1;
		}
		else r = m;
	}

	//m is the index of the stair after the last it would fit on top of
	//m is the index of the stair where the current city should be put

	int returned = fits_on_top(stairs.size() - 1, city);

	if ((l == stairs.size() - 1) && (returned != -2)) //needs a new stair
	{
		last[city.index] = returned;
		stairs.push_back({ city });
	}
	else
	{
		insert_to_stair(l, city);
	}
}

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

	//ifstream fin("be2.txt");

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

	last.resize(n, -1);

	for (int i = 0; i < n; i++)
	{
		cin >> slave >> gold;

		process({ slave, gold, i });
	}

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

	vector<int> out(stairs.size() - 1);

	int c = stairs[stairs.size() - 1].begin().operator*().index;
	for (int i = stairs.size() - 2; i >= 0; i--)
	{
		out[i] = c;
		c = last[c];
	}

	for (i = 0; i < out.size(); i++)
	{
		cout << out[i]+1 << ' ';
	}
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base100/100
1Elfogadva0/02ms356 KiB
2Elfogadva0/057ms784 KiB
3Elfogadva4/43ms356 KiB
4Elfogadva4/42ms360 KiB
5Elfogadva4/43ms368 KiB
6Elfogadva4/43ms356 KiB
7Elfogadva4/42ms368 KiB
8Elfogadva4/42ms356 KiB
9Elfogadva4/42ms356 KiB
10Elfogadva4/43ms500 KiB
11Elfogadva4/47ms400 KiB
12Elfogadva4/412ms348 KiB
13Elfogadva6/610ms524 KiB
14Elfogadva6/621ms484 KiB
15Elfogadva6/632ms536 KiB
16Elfogadva6/657ms668 KiB
17Elfogadva6/671ms740 KiB
18Elfogadva6/683ms776 KiB
19Elfogadva6/697ms796 KiB
20Elfogadva6/6123ms1056 KiB
21Elfogadva6/6125ms1156 KiB
22Elfogadva6/6123ms1124 KiB