Submission #60507

#	Time	Username	Problem	Language	Result	Execution time	Memory
60507		Eae02	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1098 ms	129124 KiB

skyscraper

#include <bits/stdc++.h>

#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)

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::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);
	}
	
	std::queue<QEntry> q;
	
	q.push(QEntry { dogePositions[0], 0, 0, true });
	q.push(QEntry { dogePositions[0], 0, 0, false });
	
	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;
		}
		
		for (int nextDoge : dogesInBuildings[entry.building])
		{
			int pBuilding = (int)entry.building - dogePowers[nextDoge];
			if (pBuilding >= 0)
				q.push(QEntry { pBuilding, nextDoge, entry.cost + 1, true });
			
			int nBuilding = (int)entry.building + dogePowers[nextDoge];
			if (nBuilding < numBuildings)
				q.push(QEntry { nBuilding, nextDoge, entry.cost + 1, false });
		}
		dogesInBuildings[entry.building].clear();
		
		if (entry.left())
		{
			int pBuilding = (int)entry.building - dogePowers[entry.doge()];
			if (pBuilding >= 0)
			{
				q.push(QEntry { pBuilding, entry.doge(), entry.cost + 1, true });
			}
		}
		else
		{
			int nBuilding = (int)entry.building + dogePowers[entry.doge()];
			if (nBuilding < numBuildings)
			{
				q.push(QEntry { nBuilding, entry.doge(), entry.cost + 1, false });
			}
		}
	}
	
	std::cout << "-1" << std::endl;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:52: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:53: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:70:63: warning: narrowing conversion of 'pBuilding' from 'int' to 'uint16_t {aka short unsigned int}' inside { } [-Wnarrowing]
     q.push(QEntry { pBuilding, nextDoge, entry.cost + 1, true });
                                                               ^
skyscraper.cpp:70:63: warning: narrowing conversion of 'nextDoge' from 'int' to 'uint16_t {aka short unsigned int}' inside { } [-Wnarrowing]
skyscraper.cpp:74:64: warning: narrowing conversion of 'nBuilding' from 'int' to 'uint16_t {aka short unsigned int}' inside { } [-Wnarrowing]
     q.push(QEntry { nBuilding, nextDoge, entry.cost + 1, false });
                                                                ^
skyscraper.cpp:74:64: warning: narrowing conversion of 'nextDoge' from 'int' to 'uint16_t {aka short unsigned int}' inside { } [-Wnarrowing]
skyscraper.cpp:83:67: warning: narrowing conversion of 'pBuilding' from 'int' to 'uint16_t {aka short unsigned int}' inside { } [-Wnarrowing]
     q.push(QEntry { pBuilding, entry.doge(), entry.cost + 1, true });
                                                                   ^
skyscraper.cpp:91:68: warning: narrowing conversion of 'nBuilding' from 'int' to 'uint16_t {aka short unsigned int}' inside { } [-Wnarrowing]
     q.push(QEntry { nBuilding, entry.doge(), entry.cost + 1, false });
                                                                    ^

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