Submission #60502

#	Time	Username	Problem	Language	Result	Execution time	Memory
60502		Eae02	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	10 / 100	4 ms	636 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)

#define push push_back

int main()
{
	int numBuildings, numDoges;
	std::cin >> numBuildings;
	std::cin >> numDoges;
	
	std::vector<std::vector<int>> dogesInBuildings(numBuildings);
	
	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::vector<QEntry> q;
	q.reserve(numBuildings * numDoges);
	
	q.push(QEntry { dogePositions[0], 0, 0, true });
	q.push(QEntry { dogePositions[0], 0, 0, false });
	
	while (!q.empty())
	{
		QEntry entry = q.back();
		q.pop_back();
		
		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:53: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:54: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:71: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:71:63: warning: narrowing conversion of 'nextDoge' from 'int' to 'uint16_t {aka short unsigned int}' inside { } [-Wnarrowing]
skyscraper.cpp:75: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:75:64: warning: narrowing conversion of 'nextDoge' from 'int' to 'uint16_t {aka short unsigned int}' inside { } [-Wnarrowing]
skyscraper.cpp:84: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:92: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: 0 / 12
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43