Submission #48206

#	Time	Username	Problem	Language	Result	Execution time	Memory
48206		E869120	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1094 ms	255868 KiB

skyscraper

#include <iostream>
#include <queue>
#include <vector>
#include <map>
using namespace std;

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++) {
		cin >> A[i] >> P[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;
			for (int j = A[i] % P[i]; j < N; j += P[i]) G[i].push_back(j);
			X[i].resize(G[i].size());
			dist[i].resize(G[i].size(), (1 << 30));
			for (int j = 0; j < G[i].size(); j++) {
				if (j == 0 || j + 1 == G[i].size()) X[i][j].resize(2);
				else X[i][j].resize(4);

				int cnt = 0;
				if (j + 1 < G[i].size()) {
					X[i][j][cnt] = constant(i, j + 1); cnt++;
					X[i][j][cnt] = constant(0, G[i][j + 1]); cnt++;
				}
				if (j >= 1) {
					X[i][j][cnt] = constant(i, j - 1); cnt++;
					X[i][j][cnt] = constant(0, G[i][j - 1]); cnt++;
				}
			}
		}
		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;
		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 (dist[0][A[2]] == (1 << 30)) dist[0][A[2]] = -1;
	cout << dist[0][A[2]] << endl;
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:30:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < G[i].size(); j++) {
                    ~~^~~~~~~~~~~~~
skyscraper.cpp:31:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (j == 0 || j + 1 == G[i].size()) X[i][j].resize(2);
                   ~~~~~~^~~~~~~~~~~~~~
skyscraper.cpp:35:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (j + 1 < G[i].size()) {
         ~~~~~~^~~~~~~~~~~~~
skyscraper.cpp:49: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:56:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < X[pos1][pos2].size(); i++) {
                   ~~^~~~~~~~~~~~~~~~~~~~~~

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