oj.uz

답안 #1026245

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1026245 2024-07-17T18:25:51 Z xnqs Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 1000 ms 108016 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)*3,pos,dog);
	dist[pos][dog] = -0x3f3f3f3f;

	int iterations = 2500000;
	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)*3,
				          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)*3,
				          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)*3,
				           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)*3,
				           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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 2 ms 2908 KB Output is correct
11 Correct 4 ms 3220 KB Output is correct
12 Correct 26 ms 10844 KB Output is correct
13 Correct 40 ms 10764 KB Output is correct
14 Correct 11 ms 2908 KB Output is correct
15 Correct 7 ms 2908 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 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 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 2648 KB Output is correct
10 Correct 2 ms 2908 KB Output is correct
11 Correct 4 ms 3288 KB Output is correct
12 Correct 26 ms 10752 KB Output is correct
13 Correct 32 ms 10772 KB Output is correct
14 Correct 8 ms 2904 KB Output is correct
15 Correct 7 ms 3044 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 23 ms 3680 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Execution timed out 1102 ms 107844 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2736 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 2648 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 2696 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 2 ms 2908 KB Output is correct
11 Correct 4 ms 3100 KB Output is correct
12 Correct 26 ms 10832 KB Output is correct
13 Correct 32 ms 10916 KB Output is correct
14 Correct 10 ms 2904 KB Output is correct
15 Correct 7 ms 2908 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 21 ms 3648 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2736 KB Output is correct
20 Execution timed out 1094 ms 107884 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2904 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 2808 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 2740 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 2 ms 2904 KB Output is correct
11 Correct 4 ms 3164 KB Output is correct
12 Correct 27 ms 10884 KB Output is correct
13 Correct 32 ms 10836 KB Output is correct
14 Correct 8 ms 2904 KB Output is correct
15 Correct 8 ms 3116 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 21 ms 3680 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 2 ms 2648 KB Output is correct
20 Execution timed out 1084 ms 108016 KB Time limit exceeded
21 Halted 0 ms 0 KB -