oj.uz

답안 #1026243

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1026243 2024-07-17T18:24:43 Z xnqs Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 1000 ms 126296 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 = 3000000;
	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 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 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 2648 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 3164 KB Output is correct
12 Correct 26 ms 10844 KB Output is correct
13 Correct 32 ms 10836 KB Output is correct
14 Correct 9 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 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 5 ms 3164 KB Output is correct
12 Correct 27 ms 10908 KB Output is correct
13 Correct 34 ms 10844 KB Output is correct
14 Correct 8 ms 2908 KB Output is correct
15 Correct 7 ms 3032 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 21 ms 3804 KB Output is correct
18 Correct 1 ms 2648 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Execution timed out 1093 ms 126296 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2660 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 2848 KB Output is correct
11 Correct 4 ms 3164 KB Output is correct
12 Correct 31 ms 10844 KB Output is correct
13 Correct 33 ms 10900 KB Output is correct
14 Correct 8 ms 3056 KB Output is correct
15 Correct 7 ms 3080 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 21 ms 3796 KB Output is correct
18 Correct 1 ms 2740 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Execution timed out 1107 ms 122732 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 43.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 2816 KB Output is correct
10 Correct 2 ms 2908 KB Output is correct
11 Correct 5 ms 3160 KB Output is correct
12 Correct 32 ms 10836 KB Output is correct
13 Correct 35 ms 10840 KB Output is correct
14 Correct 8 ms 2908 KB Output is correct
15 Correct 8 ms 3036 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 23 ms 3712 KB Output is correct
18 Correct 1 ms 2740 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Execution timed out 1100 ms 117236 KB Time limit exceeded
21 Halted 0 ms 0 KB -