제출 #60551

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
60551		Eae02	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1067 ms	2492 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);
    	
    	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])
    		{
              if (dogePowers[nextDoge] == dogePowers[entry.doge()])
					continue;
    			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;
    }

컴파일 시 표준 에러 (stderr) 메시지

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:50:51: 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:51: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(QEntry { dogePositions[0], 0, 0, false });
                                                    ^
skyscraper.cpp:70:67: 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:67: warning: narrowing conversion of 'nextDoge' from 'int' to 'uint16_t {aka short unsigned int}' inside { } [-Wnarrowing]
skyscraper.cpp:74:68: 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:68: warning: narrowing conversion of 'nextDoge' from 'int' to 'uint16_t {aka short unsigned int}' inside { } [-Wnarrowing]
skyscraper.cpp:83:71: 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:72: 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