Submission #48214

#	Time	Username	Problem	Language	Result	Execution time	Memory
48214		E869120	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	659 ms	50284 KiB

skyscraper

#include <iostream>
#include <queue>
#include <vector>
#include <map>
using namespace std;
#pragma warning (disable: 4996)

int N, M, A[30009], P[30009]; vector<short>G[30009]; vector<int>dist[30009]; vector<vector<int>> X[30009];
map<pair<int, int>, int>M1; queue<pair<int, int>>Q;

void connect(int px, int py, int qx, int qy) {
	X[px][py].emplace_back((qx << 15) + qy);
}
int constant(int u1, int u2) {
	return (u1 << 15) + u2;
}

int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) G[0].push_back(i);
	X[0].resize(G[0].size());
	dist[0].resize(G[0].size(), (1 << 30));

	for (int i = 1; i <= M; i++) scanf("%d%d", &A[i], &P[i]);
	for (int i = 1; i <= M; i++) {
		int J = M1[make_pair(A[i] % P[i], P[i])];
		if (J == 0) {
			M1[make_pair(A[i] % P[i], P[i])] = i; J = i; int BB = A[i] % P[i];
			G[i].resize(((N - 1) - BB) / P[i] + 1);
			int CC = 0; for (int j = A[i] % P[i]; j < N; j += P[i]) { G[i][CC] = j; CC++; }

			dist[i].resize(G[i].size(), (1 << 30));
		}
		int pos1 = lower_bound(G[J].begin(), G[J].end(), A[i]) - G[J].begin();
		if (A[i] + P[i] < N) connect(0, A[i], 0, A[i] + P[i]);
		if (A[i] - P[i] >= 0) connect(0, A[i], 0, A[i] - P[i]);
		if (pos1 >= 1) connect(0, A[i], J, pos1 - 1);
		if (pos1 + 1 < G[J].size()) connect(0, A[i], J, pos1 + 1);
	}
	dist[0][A[1]] = 0; Q.push(make_pair(0, A[1]));

	while (!Q.empty()) {
		int pos1 = Q.front().first, pos2 = Q.front().second; Q.pop();
		if (pos1 == 0 && pos2 == A[2]) break;
		if (pos1 == 0) {
			for (int i = 0; i < X[pos1][pos2].size(); i++) {
				int D = X[pos1][pos2][i];
				int to1 = (D >> 15), to2 = (D & 32767);
				if (dist[to1][to2] > dist[pos1][pos2] + 1) {
					dist[to1][to2] = dist[pos1][pos2] + 1;
					Q.push(make_pair(to1, to2));
				}
			}
		}
		if (pos1 >= 1) {
			for (int j = -1; j <= 1; j += 2) {
				int to1 = pos1, to2 = pos2 + j; if (to2 < 0 || to2 >= G[pos1].size()) continue;
				if (dist[to1][to2] > dist[pos1][pos2] + 1) {
					dist[to1][to2] = dist[pos1][pos2] + 1;
					Q.push(make_pair(to1, to2));
				}
			}
			for (int j = -1; j <= 1; j += 2) {
				int to1 = pos1, to2 = pos2 + j; if (to2 < 0 || to2 >= G[pos1].size()) continue;
				to2 = G[to1][to2]; to1 = 0;
				if (dist[to1][to2] > dist[pos1][pos2] + 1) {
					dist[to1][to2] = dist[pos1][pos2] + 1;
					Q.push(make_pair(to1, to2));
				}
			}
		}
	}
	if (dist[0][A[2]] == (1 << 30)) dist[0][A[2]] = -1;
	cout << dist[0][A[2]] << endl;
	return 0;
}

Compilation message (stderr)

skyscraper.cpp:6:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:38:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (pos1 + 1 < G[J].size()) connect(0, A[i], J, pos1 + 1);
       ~~~~~~~~~^~~~~~~~~~~~~
skyscraper.cpp:46:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < X[pos1][pos2].size(); i++) {
                    ~~^~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:57:56: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     int to1 = pos1, to2 = pos2 + j; if (to2 < 0 || to2 >= G[pos1].size()) continue;
                                                    ~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:64:56: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     int to1 = pos1, to2 = pos2 + j; if (to2 < 0 || to2 >= G[pos1].size()) continue;
                                                    ~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:24:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= M; i++) scanf("%d%d", &A[i], &P[i]);
                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 43 / 43