Submission #60483

#	Time	Username	Problem	Language	Result	Execution time	Memory
60483		Eae02	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1071 ms	2840 KiB

skyscraper

#include <bits/stdc++.h>

struct QEntry
{
	uint16_t building;
	uint16_t doge;
	int cost;
	bool left;
};

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

//std::bitset<30000> dogesUsed;

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)
			dogesInBuildings[dogePositions[i]].push_back(i);
	}
	
	std::deque<QEntry> q;
	
	q.push_back(QEntry { dogePositions[0], 0, 0, true });
	q.push_back(QEntry { dogePositions[0], 0, 0, false });
	//visited[dogePositions[0]][0] = true;
	//dogesUsed[0] = true;
	
	while (!q.empty())
	{
		QEntry entry = q.front();
		q.pop_front();
		
		if (entry.doge == 1 || dogePositions[1] == entry.building)
		{
			std::cout << entry.cost << std::endl;
			return 0;
		}
		
		if (!dogesInBuildings[entry.building].empty())
		{
			int nextDoge = dogesInBuildings[entry.building].back();
			dogesInBuildings[entry.building].pop_back();
			//visited[entry.building][nextDoge] = true;
			q.push_front(QEntry { entry.building, nextDoge, entry.cost, true });
			q.push_front(QEntry { entry.building, nextDoge, entry.cost, false });
		}
		
		if (entry.left)
		{
			int pBuilding = (int)entry.building - dogePowers[entry.doge];
			if (pBuilding >= 0)
			{
				q.push_back(QEntry { pBuilding, entry.doge, entry.cost + 1, true });
			}
		}
		else
		{
			int nBuilding = (int)entry.building + dogePowers[entry.doge];
			if (nBuilding < numBuildings)
			{
				q.push_back(QEntry { nBuilding, entry.doge, entry.cost + 1, false });
			}
		}
	}
	
	std::cout << "-1" << std::endl;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:36:52: 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_back(QEntry { dogePositions[0], 0, 0, true });
                                                    ^
skyscraper.cpp:37:53: 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_back(QEntry { dogePositions[0], 0, 0, false });
                                                     ^
skyscraper.cpp:57:69: warning: narrowing conversion of 'nextDoge' from 'int' to 'uint16_t {aka short unsigned int}' inside { } [-Wnarrowing]
    q.push_front(QEntry { entry.building, nextDoge, entry.cost, true });
                                                                     ^
skyscraper.cpp:58:70: warning: narrowing conversion of 'nextDoge' from 'int' to 'uint16_t {aka short unsigned int}' inside { } [-Wnarrowing]
    q.push_front(QEntry { entry.building, nextDoge, entry.cost, false });
                                                                      ^
skyscraper.cpp:66:70: warning: narrowing conversion of 'pBuilding' from 'int' to 'uint16_t {aka short unsigned int}' inside { } [-Wnarrowing]
     q.push_back(QEntry { pBuilding, entry.doge, entry.cost + 1, true });
                                                                      ^
skyscraper.cpp:74:71: warning: narrowing conversion of 'nBuilding' from 'int' to 'uint16_t {aka short unsigned int}' inside { } [-Wnarrowing]
     q.push_back(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