Submission #60525

#	Time	Username	Problem	Language	Result	Execution time	Memory
60525		Eae02	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1091 ms	214268 KiB

skyscraper

#include <bits/stdc++.h>

#pragma GCC optimize("O3")

#pragma pack(push, 1)
struct QEntry
{
	uint16_t building;
	uint16_t dogeAndL;
	int cost;
	
	QEntry(uint16_t building, uint16_t doge, int cost, bool left)
	{
		this->building = building;
		this->cost = cost;
		this->dogeAndL = (doge << 1) | (left ? 1 : 0);
	}
	
	bool left()
	{
		return dogeAndL & 0x1;
	}
	
	uint16_t doge()
	{
		return dogeAndL >> 1;
	}
};
#pragma pack(pop)

std::bitset<30000> visited[30000];

int main()
{
	int numBuildings, numDoges;
	std::cin >> numBuildings;
	std::cin >> numDoges;
	
	std::vector<std::vector<int>> dogesInBuildings(numBuildings);
	for (int i = 0; i < numBuildings; i++)
		dogesInBuildings[i].reserve(numDoges);
	
	std::set<int> filledBuildings;
	
	std::vector<int> dogePositions(numDoges);
	std::vector<int> dogePowers(numDoges);
	for (int i = 0; i < numDoges; i++)
	{
		std::cin >> dogePositions[i];
		std::cin >> dogePowers[i];
		
		if (i != 0 && (i == 1 || dogePositions[i] - dogePowers[i] >= 0 || dogePositions[i] + dogePowers[i] < numBuildings))
		{
			dogesInBuildings[dogePositions[i]].push_back(i);
			
			filledBuildings.insert(dogePositions[i]);
		}
	}
	
	std::queue<QEntry> q;
	
	q.push(QEntry { dogePositions[0], 0, 0, true });
	q.push(QEntry { dogePositions[0], 0, 0, false });
	
	auto MaybePush = [&] (int b, int d, int c, bool l)
	{
		if (!visited[b][d])
		{
			visited[b][d] = true;
			q.push(QEntry { b, d, c, l });
		}
	};
	
	while (!q.empty())
	{
		QEntry entry = q.front();
		q.pop();
		
		if (entry.doge() == 1 || dogePositions[1] == entry.building)
		{
			std::cout << entry.cost << std::endl;
			return 0;
		}
		
		if (!dogesInBuildings[entry.building].empty())
		{
			for (int nextDoge : dogesInBuildings[entry.building])
			{
				int pBuilding = (int)entry.building - dogePowers[nextDoge];
				if (pBuilding >= 0)
					MaybePush(pBuilding, nextDoge, entry.cost + 1, true);
				
				int nBuilding = (int)entry.building + dogePowers[nextDoge];
				if (nBuilding < numBuildings)
					MaybePush(nBuilding, nextDoge, entry.cost + 1, false);
			}
			dogesInBuildings[entry.building].clear();
			filledBuildings.erase(entry.building);
		}
		
		if (entry.left())
		{
			int pBuilding = (int)entry.building - dogePowers[entry.doge()];
			if (pBuilding >= 0)
			{
				if (*filledBuildings.begin() <= pBuilding)
				{
					MaybePush(pBuilding, entry.doge(), entry.cost + 1, true);
				}
			}
		}
		else
		{
			int nBuilding = (int)entry.building + dogePowers[entry.doge()];
			if (nBuilding < numBuildings)
			{
				if (*std::prev(filledBuildings.end()) >= nBuilding)
				{
					MaybePush(nBuilding, entry.doge(), entry.cost + 1, false);
				}
			}
		}
	}
	
	std::cout << "-1" << std::endl;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:62:47: warning: narrowing conversion of 'dogePositions.std::vector<int>::operator[](0)' from '__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type {aka int}' to 'uint16_t {aka short unsigned int}' inside { } [-Wnarrowing]
  q.push(QEntry { dogePositions[0], 0, 0, true });
                                               ^
skyscraper.cpp:63:48: warning: narrowing conversion of 'dogePositions.std::vector<int>::operator[](0)' from '__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type {aka int}' to 'uint16_t {aka short unsigned int}' inside { } [-Wnarrowing]
  q.push(QEntry { dogePositions[0], 0, 0, false });
                                                ^
skyscraper.cpp: In lambda function:
skyscraper.cpp:70:31: warning: narrowing conversion of 'b' from 'int' to 'uint16_t {aka short unsigned int}' inside { } [-Wnarrowing]
    q.push(QEntry { b, d, c, l });
                               ^
skyscraper.cpp:70:31: warning: narrowing conversion of 'd' from 'int' to 'uint16_t {aka short unsigned int}' inside { } [-Wnarrowing]

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 0 / 43