답안 #472048

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
472048	2021-09-12T13:46:58 Z	hhhhaura	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	22 / 100	176 ms	262148 KB

skyscraper

#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)

#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i --)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))

#define INF 1000000000
#define MOD 1000000007
#define eps (1e-9)

using namespace std;

#define lld long double
#define pii pair<int, int> 
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())

#ifdef wiwihorz
#define print(a...) cerr << "Line " << __LINE__ << ": ", kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) {while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
void kout() { cerr << endl; }
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...); }
#else
#define print(...) 0
#define vprint(...) 0
#endif
namespace solver {
	const int P = 5000000;
	const int K = 140;
	int n, m, st, ed, ii;
	vector<int> dis, s;
	vector<vector<int>> mp1, mp0;
	
	vector<vector<vector<int>>> a;
	void init_(int _n, int _m) {
		n = _n, m = _m, ii = n - 1;
		s.clear();
		dis.assign(P, INF);
		mp1.assign(P, vector<int>());
		mp0.assign(P, vector<int>());
		rep(i, 0, K - 1) a.push_back(vector<vector<int>>(i, vector<int>()));
	}
	void get_new() {
		ii++;
		if(ii >= P) exit(0);
	}
	void add_node(int pos, int b) {
		for(int i = pos % b; i < n; i += b) {
			get_new();
			if(i == pos) mp0[i].push_back(ii);
			if(i != pos % b) {
				mp1[ii].push_back(ii - 1);
				mp1[ii - 1].push_back(ii);
			}
			mp0[ii].push_back(i);
		}
	}
	int solve() {
		rep(i, 1, K - 1) rep(j, 0, i - 1) {
			if(!a[i][j].size()) continue;
			sort(all(a[i][j]));
			vector<int> &v = a[i][j];
			int id = -1;
			for(int k = j; k < n; k += i) {
				get_new();
				while(id + 1 < v.size() && v[id + 1] <= k) id ++;
				if(id >= 0 && v[id] == k) mp0[k].push_back(ii);
				if(k != j) {
					mp1[ii].push_back(ii - 1);
					mp1[ii - 1].push_back(ii);
				}
				mp0[ii].push_back(k);
			}
		}
		dis[st] = 0;
		deque<int> q;
		q.push_back(st);
		while(q.size()) {
			int cur = q.front();
			q.pop_front();
			for(auto i : mp0[cur]) if(dis[i] == INF) {
				dis[i] = dis[cur];
				q.push_front(i);
			}
			for(auto i : mp1[cur]) if(dis[i] == INF) {
				dis[i] = 1 + dis[cur];
				q.push_back(i);
			}
		}
		return (dis[ed] == INF ? -1 : dis[ed]);
	}
};
using namespace solver;
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n, m, b, p; 
	cin >> n >> m;
	init_(n, m);
	rep(i, 0, m - 1) {
		cin >> b >> p;
		if(i == 0) st = b;
		if(i == 1) ed = b;
		if(p >= K) add_node(b, p);
		else a[p][b % p].push_back(b);
	} 
	cout << solve() << "\n";
	return 0;
}

Compilation message

skyscraper.cpp:4: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    4 | #pragma loop-opt(on)
      | 
skyscraper.cpp:23:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   23 | void vprint(auto L, auto R) {while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
      |             ^~~~
skyscraper.cpp:23:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   23 | void vprint(auto L, auto R) {while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
      |                     ^~~~
skyscraper.cpp: In function 'int solver::solve()':
skyscraper.cpp:69:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     while(id + 1 < v.size() && v[id + 1] <= k) id ++;
      |           ~~~~~~~^~~~~~~~~~

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	155 ms	254896 KB	Output is correct
2	Correct	160 ms	254892 KB	Output is correct
3	Correct	153 ms	254824 KB	Output is correct
4	Correct	154 ms	254848 KB	Output is correct
5	Correct	159 ms	254840 KB	Output is correct
6	Correct	154 ms	254840 KB	Output is correct
7	Correct	161 ms	255108 KB	Output is correct

Subtask #2

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	174 ms	254868 KB	Output is correct
2	Correct	158 ms	254932 KB	Output is correct
3	Correct	154 ms	254916 KB	Output is correct
4	Correct	154 ms	254824 KB	Output is correct
5	Correct	157 ms	254828 KB	Output is correct
6	Correct	174 ms	254912 KB	Output is correct
7	Correct	158 ms	254924 KB	Output is correct
8	Correct	155 ms	254944 KB	Output is correct
9	Correct	159 ms	254896 KB	Output is correct
10	Correct	157 ms	254980 KB	Output is correct
11	Correct	161 ms	255176 KB	Output is correct
12	Correct	176 ms	254900 KB	Output is correct
13	Correct	158 ms	254900 KB	Output is correct
14	Correct	156 ms	255300 KB	Output is correct
15	Correct	167 ms	255300 KB	Output is correct

Subtask #3

0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	159 ms	254876 KB	Output is correct
2	Correct	152 ms	254908 KB	Output is correct
3	Correct	155 ms	254900 KB	Output is correct
4	Correct	154 ms	254836 KB	Output is correct
5	Correct	159 ms	254892 KB	Output is correct
6	Correct	157 ms	254916 KB	Output is correct
7	Correct	155 ms	254892 KB	Output is correct
8	Correct	159 ms	254916 KB	Output is correct
9	Correct	175 ms	254860 KB	Output is correct
10	Correct	158 ms	254956 KB	Output is correct
11	Correct	158 ms	255408 KB	Output is correct
12	Correct	156 ms	254868 KB	Output is correct
13	Correct	161 ms	254892 KB	Output is correct
14	Correct	159 ms	255272 KB	Output is correct
15	Correct	157 ms	255384 KB	Output is correct
16	Correct	173 ms	255148 KB	Output is correct
17	Correct	154 ms	255812 KB	Output is correct
18	Correct	156 ms	255384 KB	Output is correct
19	Correct	159 ms	255176 KB	Output is correct
20	Correct	159 ms	255052 KB	Output is correct
21	Correct	155 ms	255060 KB	Output is correct
22	Correct	161 ms	255428 KB	Output is correct
23	Correct	153 ms	255348 KB	Output is correct
24	Correct	161 ms	255684 KB	Output is correct
25	Correct	156 ms	255428 KB	Output is correct
26	Correct	159 ms	255456 KB	Output is correct
27	Correct	161 ms	255368 KB	Output is correct
28	Correct	174 ms	256324 KB	Output is correct
29	Correct	165 ms	258688 KB	Output is correct
30	Correct	156 ms	255980 KB	Output is correct
31	Correct	166 ms	256960 KB	Output is correct
32	Correct	169 ms	256424 KB	Output is correct
33	Runtime error	159 ms	262148 KB	Execution killed with signal 9
34	Halted	0 ms	0 KB	-

Subtask #4

0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	167 ms	254840 KB	Output is correct
2	Correct	154 ms	254924 KB	Output is correct
3	Correct	153 ms	254880 KB	Output is correct
4	Correct	172 ms	254916 KB	Output is correct
5	Correct	156 ms	254924 KB	Output is correct
6	Correct	154 ms	254952 KB	Output is correct
7	Correct	172 ms	254864 KB	Output is correct
8	Correct	153 ms	254920 KB	Output is correct
9	Correct	157 ms	255048 KB	Output is correct
10	Correct	160 ms	254952 KB	Output is correct
11	Correct	176 ms	255264 KB	Output is correct
12	Correct	152 ms	254916 KB	Output is correct
13	Correct	159 ms	254884 KB	Output is correct
14	Correct	169 ms	255308 KB	Output is correct
15	Correct	156 ms	255348 KB	Output is correct
16	Correct	157 ms	255204 KB	Output is correct
17	Correct	157 ms	255900 KB	Output is correct
18	Correct	155 ms	255284 KB	Output is correct
19	Correct	156 ms	255148 KB	Output is correct
20	Correct	155 ms	255248 KB	Output is correct
21	Correct	158 ms	255040 KB	Output is correct
22	Correct	153 ms	255280 KB	Output is correct
23	Correct	154 ms	255264 KB	Output is correct
24	Correct	158 ms	255668 KB	Output is correct
25	Correct	170 ms	255492 KB	Output is correct
26	Correct	154 ms	255412 KB	Output is correct
27	Correct	160 ms	255344 KB	Output is correct
28	Correct	162 ms	256408 KB	Output is correct
29	Correct	172 ms	258796 KB	Output is correct
30	Correct	160 ms	255940 KB	Output is correct
31	Correct	169 ms	257140 KB	Output is correct
32	Correct	166 ms	256324 KB	Output is correct
33	Runtime error	156 ms	262148 KB	Execution killed with signal 9
34	Halted	0 ms	0 KB	-

Subtask #5

0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	162 ms	254888 KB	Output is correct
2	Correct	171 ms	254868 KB	Output is correct
3	Correct	156 ms	254876 KB	Output is correct
4	Correct	154 ms	254844 KB	Output is correct
5	Correct	165 ms	254908 KB	Output is correct
6	Correct	165 ms	254844 KB	Output is correct
7	Correct	154 ms	254924 KB	Output is correct
8	Correct	155 ms	254868 KB	Output is correct
9	Correct	155 ms	254936 KB	Output is correct
10	Correct	156 ms	255040 KB	Output is correct
11	Correct	157 ms	255272 KB	Output is correct
12	Correct	153 ms	255036 KB	Output is correct
13	Correct	166 ms	254940 KB	Output is correct
14	Correct	154 ms	255292 KB	Output is correct
15	Correct	163 ms	255288 KB	Output is correct
16	Correct	155 ms	255096 KB	Output is correct
17	Correct	155 ms	255948 KB	Output is correct
18	Correct	154 ms	255380 KB	Output is correct
19	Correct	153 ms	255172 KB	Output is correct
20	Correct	153 ms	255116 KB	Output is correct
21	Correct	159 ms	255084 KB	Output is correct
22	Correct	155 ms	255300 KB	Output is correct
23	Correct	158 ms	255300 KB	Output is correct
24	Correct	164 ms	255716 KB	Output is correct
25	Correct	155 ms	255428 KB	Output is correct
26	Correct	158 ms	255428 KB	Output is correct
27	Correct	154 ms	255372 KB	Output is correct
28	Correct	163 ms	256560 KB	Output is correct
29	Correct	172 ms	258868 KB	Output is correct
30	Correct	157 ms	256016 KB	Output is correct
31	Correct	160 ms	257024 KB	Output is correct
32	Correct	163 ms	256424 KB	Output is correct
33	Runtime error	159 ms	262148 KB	Execution killed with signal 9
34	Halted	0 ms	0 KB	-