oj.uz

Submission #1023454

# Submission time Handle Problem Language Result Execution time Memory
1023454 2024-07-14T18:59:42 Z xnqs Jakarta Skyscrapers (APIO15_skyscraper) C++17
10 / 100
 2 ms 2904 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <unordered_map>

int x, dog_cnt;
std::vector<std::pair<int,int>> dogs; 
std::unordered_map<int,int> dist[30005];
std::vector<int> dogs_in[30005];

int astar(int pos, int dog) {
	std::priority_queue<std::tuple<int,int,int>, std::vector<std::tuple<int,int,int>>, std::greater<std::tuple<int,int,int>>> pq;
	pq.emplace(0+std::abs(pos-dogs[1].first),pos,dog);
	dist[pos][dog] = 0;

	int iterations = 2000000;
	while (!pq.empty()&&iterations--) {
		auto [c, pos, dog] = pq.top();
		pq.pop();

		if (pos-dogs[dog].second>=0) {
			if (!dist[pos-dogs[dog].second].count(dog)||dist[pos-dogs[dog].second][dog]>dist[pos][dog]+1) {
				dist[pos-dogs[dog].second][dog] = dist[pos][dog]+1;
				pq.emplace(dist[pos-dogs[dog].second][dog]+std::abs((pos-dogs[dog].second)-dogs[1].first),
				          pos-dogs[dog].second,
				          dog);
			}
		}
		if (pos+dogs[dog].second<x) {
			if (!dist[pos+dogs[dog].second].count(dog)||dist[pos+dogs[dog].second][dog]>dist[pos][dog]+1) {
				dist[pos+dogs[dog].second][dog] = dist[pos][dog]+1;
				pq.emplace(dist[pos+dogs[dog].second][dog]+std::abs((pos+dogs[dog].second)-dogs[1].first),
				          pos+dogs[dog].second,
				          dog);
			}
		}

		if (!dogs_in[pos].empty()) {
			int next_idx = std::lower_bound(dogs_in[pos].begin(),dogs_in[pos].end(),dog)-dogs_in[pos].begin();
			if (next_idx==dogs_in[pos].size()||dogs_in[pos][next_idx]>dog) {
				next_idx = 0;
			}

			next_idx = dogs_in[pos][next_idx];
			if (!dist[pos].count(next_idx)||dist[pos][next_idx]>dist[pos][dog]) {
				dist[pos][next_idx] = dist[pos][dog];
				pq.emplace(dist[pos][next_idx]+std::abs(pos-dogs[1].first),
				           pos,
				           next_idx);
			}

			next_idx = dogs_in[pos][0];
			if (!dist[pos].count(next_idx)||dist[pos][next_idx]>dist[pos][dog]) {
				dist[pos][next_idx] = dist[pos][dog];
				pq.emplace(dist[pos][next_idx]+std::abs(pos-dogs[1].first),
				           pos,
				           next_idx);
			}
		}
	}

	int min = 0x3f3f3f3f;
	for (int i = 0; i < dog_cnt; i++) {
		if (!dist[dogs[1].first].count(i)) {
			continue;
		}

		min = std::min(min, dist[dogs[1].first][i]);
	}

	return ((min==0x3f3f3f3f) ? -1 : min);
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> x >> dog_cnt;
	dogs.reserve(dog_cnt);

	for (int i = 0, a, b; i < dog_cnt; i++) {
		std::cin >> a >> b;
		dogs.emplace_back(a,b);
		dogs_in[a].emplace_back(i);
	}

	for (int i = 0; i < 30005; i++) {
		std::sort(dogs_in[i].begin(),dogs_in[i].end());
	}

	std::cout << astar(dogs[0].first, 0) << "\n";
}

Compilation message

skyscraper.cpp: In function 'int astar(int, int)':
skyscraper.cpp:43:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |    if (next_idx==dogs_in[pos].size()||dogs_in[pos][next_idx]>dog) {
      |        ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Incorrect 2 ms 2652 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 2 ms 2904 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Incorrect 1 ms 2652 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2772 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2700 KB Output is correct
9 Incorrect 1 ms 2652 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Incorrect 2 ms 2652 KB Output isn't correct
10 Halted 0 ms 0 KB -