oj.uz

Submission #1026259

# Submission time Handle Problem Language Result Execution time Memory
1026259 2024-07-17T18:34:36 Z xnqs Jakarta Skyscrapers (APIO15_skyscraper) C++17
36 / 100
 687 ms 88584 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(-0x3f3f3f3f+std::abs(pos-dogs[1].first)/dogs[dog].second,pos,dog);
	dist[pos][dog] = -0x3f3f3f3f;

	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)/dogs[dog].second,
				          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)/dogs[dog].second,
				          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+1>=dogs_in[pos].size()||dogs_in[pos][next_idx]!=dog) {
				next_idx = -1;
			}

			next_idx = dogs_in[pos][next_idx+1];
			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)/dogs[dog].second,
				           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)/dogs[dog].second,
				           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]+0x3f3f3f3f);
	}

	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:18: 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+1>=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 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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2712 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 2 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 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2908 KB Output is correct
11 Correct 5 ms 3160 KB Output is correct
12 Correct 32 ms 10844 KB Output is correct
13 Correct 33 ms 10824 KB Output is correct
14 Correct 3 ms 2904 KB Output is correct
15 Correct 3 ms 3040 KB Output is correct

Subtask #3
14.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 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 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 4 ms 3164 KB Output is correct
12 Correct 26 ms 10836 KB Output is correct
13 Correct 54 ms 10832 KB Output is correct
14 Correct 3 ms 2908 KB Output is correct
15 Correct 3 ms 2908 KB Output is correct
16 Correct 1 ms 2824 KB Output is correct
17 Correct 9 ms 3628 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 366 ms 88496 KB Output is correct
21 Correct 1 ms 2652 KB Output is correct
22 Correct 1 ms 2652 KB Output is correct
23 Correct 3 ms 3164 KB Output is correct
24 Correct 8 ms 3416 KB Output is correct
25 Correct 9 ms 3164 KB Output is correct
26 Correct 266 ms 86104 KB Output is correct
27 Correct 297 ms 87272 KB Output is correct
28 Correct 5 ms 3676 KB Output is correct
29 Correct 15 ms 5640 KB Output is correct
30 Correct 4 ms 3416 KB Output is correct
31 Correct 7 ms 4188 KB Output is correct
32 Correct 4 ms 3676 KB Output is correct
33 Correct 35 ms 8440 KB Output is correct
34 Correct 45 ms 8568 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2740 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 Correct 2 ms 2648 KB Output is correct
10 Correct 1 ms 2912 KB Output is correct
11 Correct 6 ms 3164 KB Output is correct
12 Correct 43 ms 10836 KB Output is correct
13 Correct 34 ms 10832 KB Output is correct
14 Correct 3 ms 2908 KB Output is correct
15 Correct 4 ms 2908 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 9 ms 3676 KB Output is correct
18 Correct 1 ms 2648 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 360 ms 88584 KB Output is correct
21 Correct 1 ms 2648 KB Output is correct
22 Correct 1 ms 2652 KB Output is correct
23 Correct 2 ms 3196 KB Output is correct
24 Correct 5 ms 3420 KB Output is correct
25 Correct 9 ms 3216 KB Output is correct
26 Correct 260 ms 85900 KB Output is correct
27 Correct 278 ms 87404 KB Output is correct
28 Correct 5 ms 3676 KB Output is correct
29 Correct 14 ms 5556 KB Output is correct
30 Correct 3 ms 3416 KB Output is correct
31 Correct 9 ms 4184 KB Output is correct
32 Correct 5 ms 3676 KB Output is correct
33 Correct 42 ms 8592 KB Output is correct
34 Correct 34 ms 8560 KB Output is correct
35 Correct 67 ms 9600 KB Output is correct
36 Correct 9 ms 3676 KB Output is correct
37 Correct 211 ms 16420 KB Output is correct
38 Correct 148 ms 13648 KB Output is correct
39 Correct 135 ms 14928 KB Output is correct
40 Incorrect 687 ms 6876 KB Output isn't correct
41 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 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 2648 KB Output is correct
7 Correct 1 ms 2900 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 5 ms 3176 KB Output is correct
12 Correct 34 ms 10672 KB Output is correct
13 Correct 33 ms 10832 KB Output is correct
14 Correct 3 ms 2908 KB Output is correct
15 Correct 3 ms 2908 KB Output is correct
16 Correct 1 ms 2716 KB Output is correct
17 Correct 8 ms 3676 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2648 KB Output is correct
20 Correct 359 ms 88552 KB Output is correct
21 Correct 1 ms 2648 KB Output is correct
22 Correct 1 ms 2652 KB Output is correct
23 Correct 3 ms 3160 KB Output is correct
24 Correct 5 ms 3420 KB Output is correct
25 Correct 9 ms 3164 KB Output is correct
26 Correct 279 ms 86064 KB Output is correct
27 Correct 283 ms 87180 KB Output is correct
28 Correct 5 ms 3820 KB Output is correct
29 Correct 14 ms 5724 KB Output is correct
30 Correct 3 ms 3420 KB Output is correct
31 Correct 9 ms 4240 KB Output is correct
32 Correct 4 ms 3676 KB Output is correct
33 Correct 35 ms 8532 KB Output is correct
34 Correct 35 ms 8540 KB Output is correct
35 Correct 67 ms 9600 KB Output is correct
36 Correct 9 ms 3672 KB Output is correct
37 Correct 189 ms 16468 KB Output is correct
38 Correct 150 ms 13648 KB Output is correct
39 Correct 132 ms 14932 KB Output is correct
40 Incorrect 668 ms 6916 KB Output isn't correct
41 Halted 0 ms 0 KB -