113362024-08-20 08:53:38GervidHadjáratcpp17Wrong answer 54/100122ms2148 KiB
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <limits.h>
#include <algorithm>
#include <math.h>

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} } };

bool 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 false; //if it doesn't exists, the city won't fit on top
	
	if (prev(it).operator*().gold < city.gold) return true; //if the step is smaller in gold too, the city fits on top of it
	else return false;
}

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;

		if (fits_on_top(m, city)) 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

	if (l == stairs.size() - 1 && fits_on_top(stairs.size()-1, city)) //needs a new stair
	{
		stairs.push_back({ city });
	}
	else
	{
		insert_to_stair(l, city);
	}
}

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

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


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

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

	//backtracking, answering

	City current = stairs[stairs.size() - 1].begin().operator*();
	vector<int> out = {current.index};
	out.reserve(stairs.size());

	for (int i = stairs.size() - 2; i >= 1; i--)
	{
		current = prev(stairs[i].lower_bound(current)).operator*();
		out.push_back(current.index);
	}

	cout << out.size() << '\n';

	for (int i = out.size() - 1; i >= 0; i--)
	{
		cout << out[i]+1 << ' ';
	}
}
SubtaskSumTestVerdictTimeMemory
base54/100
1Accepted0/03ms560 KiB
2Wrong answer0/056ms1224 KiB
3Accepted4/43ms528 KiB
4Partially correct2/43ms652 KiB
5Partially correct2/43ms488 KiB
6Accepted4/42ms356 KiB
7Partially correct2/42ms376 KiB
8Partially correct2/43ms404 KiB
9Partially correct2/43ms492 KiB
10Partially correct2/43ms356 KiB
11Partially correct2/47ms500 KiB
12Partially correct2/410ms612 KiB
13Partially correct3/610ms584 KiB
14Partially correct3/620ms612 KiB
15Partially correct3/632ms828 KiB
16Partially correct3/657ms1068 KiB
17Partially correct3/670ms1328 KiB
18Partially correct3/682ms1464 KiB
19Partially correct3/696ms1764 KiB
20Partially correct3/6122ms1884 KiB
21Partially correct3/6122ms2020 KiB
22Partially correct3/6122ms2148 KiB