oj.uz

Submission #558809

# Submission time Handle Problem Language Result Execution time Memory
558809 2022-05-08T12:15:33 Z hhhhaura Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 159 ms 150032 KB 
#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse")
#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 lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
#define INF 1000000000
#define MOD 1000000007
#define eps (1e-9)
using namespace std;
#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
#define x first
#define y second
namespace solver {
	int n, m, s, t, ii;
	const int P = 180, mx = 1000000;
	vector<pii> mp[mx], a;
	vector<int> v[P + 1][P + 1];
	vector<int> dis;
	void init_(int _n, int _m) {
		ii = _n;
		n = _n, m = _m;
		a.clear();
		dis.assign(mx, INF);
	}
	void solve() {
		for(auto i : a) {
			int st = i.y % i.x;
			for(int j = st; j < n; j += i.x) {
				ii++;
				if(j != st) mp[ii].push_back({ii - 1, 1});
				if(j + i.x < n) mp[ii].push_back({ii + 1, 1});
				if(j == i.y) mp[j].push_back({ii, 0});
				mp[ii].push_back({j, 0});
			}
		}
		rep(i, 1, P) rep(j, 0, i - 1) {
			sort(all(v[i][j]));
			if(!v[i][j].size()) continue;
			int cur = 0;
			for(int k = j; k < n; k += i) {
				ii++;
				if(k != j) mp[ii].push_back({ii - 1, 1});
				if(k + i < n) mp[ii].push_back({ii + 1, 1});
				if(cur < v[i][j].size() && 
					v[i][j][cur] == k) mp[k].push_back({ii, 0}), cur++;
				mp[ii].push_back({k, 0});
			}
		}
		dis[s] = 0;
		deque<int> q;
		q.push_back(s);
		while(q.size()) {
			int cur = q.front();
			q.pop_front();
			if(cur == t) {
				cout << dis[cur] << "\n";
				return;
			}
			for(auto i : mp[cur]) {
				if(dis[i.x] != INF) continue;
				dis[i.x] = dis[cur] + i.y;
				if(i.y) q.push_back(i.x);
				else q.push_front(i.x);
			}
		}
		cout << "-1\n";
		return;

	}
};
using namespace solver;
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n, m;
	cin >> n >> m;
	init_(n, m);
	rep(i, 0, m - 1) {
		int b, p;
		cin >> b >> p;
		if(i == 0) s = b;
		if(i == 1) t = b;
		if(p <= P) v[p][b % p].push_back(b);
		else a.push_back({p, b});
	}
	solve();
	return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28500 KB Output is correct
2 Correct 15 ms 28436 KB Output is correct
3 Correct 14 ms 28500 KB Output is correct
4 Correct 14 ms 28372 KB Output is correct
5 Correct 16 ms 28500 KB Output is correct
6 Correct 14 ms 28372 KB Output is correct
7 Correct 14 ms 28500 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28436 KB Output is correct
2 Correct 14 ms 28372 KB Output is correct
3 Correct 13 ms 28500 KB Output is correct
4 Correct 14 ms 28500 KB Output is correct
5 Correct 14 ms 28412 KB Output is correct
6 Correct 13 ms 28500 KB Output is correct
7 Correct 14 ms 28432 KB Output is correct
8 Correct 14 ms 28444 KB Output is correct
9 Correct 14 ms 28500 KB Output is correct
10 Correct 14 ms 28636 KB Output is correct
11 Correct 14 ms 28680 KB Output is correct
12 Correct 14 ms 28460 KB Output is correct
13 Correct 15 ms 28428 KB Output is correct
14 Correct 14 ms 28756 KB Output is correct
15 Correct 15 ms 28756 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28456 KB Output is correct
2 Correct 14 ms 28500 KB Output is correct
3 Correct 14 ms 28420 KB Output is correct
4 Correct 14 ms 28500 KB Output is correct
5 Correct 14 ms 28500 KB Output is correct
6 Correct 14 ms 28500 KB Output is correct
7 Correct 15 ms 28420 KB Output is correct
8 Correct 14 ms 28420 KB Output is correct
9 Correct 14 ms 28500 KB Output is correct
10 Correct 13 ms 28500 KB Output is correct
11 Correct 15 ms 28628 KB Output is correct
12 Correct 14 ms 28500 KB Output is correct
13 Correct 14 ms 28504 KB Output is correct
14 Correct 15 ms 28756 KB Output is correct
15 Correct 16 ms 28804 KB Output is correct
16 Correct 14 ms 28668 KB Output is correct
17 Correct 16 ms 29140 KB Output is correct
18 Correct 15 ms 28756 KB Output is correct
19 Correct 14 ms 28660 KB Output is correct
20 Correct 15 ms 28692 KB Output is correct
21 Correct 14 ms 28552 KB Output is correct
22 Correct 15 ms 28680 KB Output is correct
23 Correct 15 ms 28808 KB Output is correct
24 Correct 16 ms 29012 KB Output is correct
25 Correct 14 ms 28812 KB Output is correct
26 Correct 16 ms 28772 KB Output is correct
27 Correct 14 ms 28756 KB Output is correct
28 Correct 16 ms 29524 KB Output is correct
29 Correct 22 ms 31332 KB Output is correct
30 Correct 18 ms 29280 KB Output is correct
31 Correct 18 ms 30024 KB Output is correct
32 Correct 17 ms 29524 KB Output is correct
33 Correct 32 ms 34096 KB Output is correct
34 Correct 29 ms 34100 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28372 KB Output is correct
2 Correct 13 ms 28500 KB Output is correct
3 Correct 13 ms 28424 KB Output is correct
4 Correct 14 ms 28500 KB Output is correct
5 Correct 14 ms 28420 KB Output is correct
6 Correct 14 ms 28480 KB Output is correct
7 Correct 13 ms 28460 KB Output is correct
8 Correct 13 ms 28424 KB Output is correct
9 Correct 16 ms 28420 KB Output is correct
10 Correct 13 ms 28500 KB Output is correct
11 Correct 15 ms 28628 KB Output is correct
12 Correct 15 ms 28480 KB Output is correct
13 Correct 14 ms 28500 KB Output is correct
14 Correct 15 ms 28812 KB Output is correct
15 Correct 14 ms 28804 KB Output is correct
16 Correct 14 ms 28696 KB Output is correct
17 Correct 15 ms 29192 KB Output is correct
18 Correct 15 ms 28756 KB Output is correct
19 Correct 14 ms 28628 KB Output is correct
20 Correct 14 ms 28676 KB Output is correct
21 Correct 14 ms 28604 KB Output is correct
22 Correct 14 ms 28672 KB Output is correct
23 Correct 15 ms 28756 KB Output is correct
24 Correct 18 ms 29012 KB Output is correct
25 Correct 15 ms 28784 KB Output is correct
26 Correct 15 ms 28884 KB Output is correct
27 Correct 15 ms 28816 KB Output is correct
28 Correct 16 ms 29580 KB Output is correct
29 Correct 26 ms 31284 KB Output is correct
30 Correct 16 ms 29208 KB Output is correct
31 Correct 19 ms 30040 KB Output is correct
32 Correct 17 ms 29524 KB Output is correct
33 Correct 34 ms 34048 KB Output is correct
34 Correct 29 ms 34132 KB Output is correct
35 Correct 31 ms 33508 KB Output is correct
36 Correct 16 ms 29396 KB Output is correct
37 Correct 40 ms 36756 KB Output is correct
38 Correct 39 ms 36172 KB Output is correct
39 Correct 36 ms 36228 KB Output is correct
40 Correct 37 ms 36220 KB Output is correct
41 Correct 39 ms 36224 KB Output is correct
42 Correct 19 ms 29092 KB Output is correct
43 Correct 18 ms 29068 KB Output is correct
44 Correct 17 ms 28884 KB Output is correct
45 Correct 141 ms 51380 KB Output is correct
46 Correct 113 ms 51536 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28528 KB Output is correct
2 Correct 14 ms 28500 KB Output is correct
3 Correct 13 ms 28500 KB Output is correct
4 Correct 14 ms 28500 KB Output is correct
5 Correct 13 ms 28372 KB Output is correct
6 Correct 13 ms 28372 KB Output is correct
7 Correct 16 ms 28448 KB Output is correct
8 Correct 14 ms 28500 KB Output is correct
9 Correct 17 ms 28500 KB Output is correct
10 Correct 15 ms 28500 KB Output is correct
11 Correct 14 ms 28732 KB Output is correct
12 Correct 15 ms 28424 KB Output is correct
13 Correct 14 ms 28500 KB Output is correct
14 Correct 15 ms 28884 KB Output is correct
15 Correct 15 ms 28812 KB Output is correct
16 Correct 14 ms 28580 KB Output is correct
17 Correct 15 ms 29140 KB Output is correct
18 Correct 15 ms 28796 KB Output is correct
19 Correct 14 ms 28620 KB Output is correct
20 Correct 14 ms 28692 KB Output is correct
21 Correct 14 ms 28552 KB Output is correct
22 Correct 15 ms 28676 KB Output is correct
23 Correct 15 ms 28756 KB Output is correct
24 Correct 16 ms 29012 KB Output is correct
25 Correct 15 ms 28884 KB Output is correct
26 Correct 14 ms 28884 KB Output is correct
27 Correct 14 ms 28756 KB Output is correct
28 Correct 17 ms 29524 KB Output is correct
29 Correct 25 ms 31368 KB Output is correct
30 Correct 15 ms 29268 KB Output is correct
31 Correct 19 ms 30024 KB Output is correct
32 Correct 17 ms 29524 KB Output is correct
33 Correct 33 ms 34056 KB Output is correct
34 Correct 34 ms 34124 KB Output is correct
35 Correct 31 ms 33508 KB Output is correct
36 Correct 16 ms 29328 KB Output is correct
37 Correct 40 ms 36684 KB Output is correct
38 Correct 40 ms 36200 KB Output is correct
39 Correct 37 ms 36164 KB Output is correct
40 Correct 39 ms 36148 KB Output is correct
41 Correct 38 ms 36216 KB Output is correct
42 Correct 20 ms 29064 KB Output is correct
43 Correct 18 ms 29140 KB Output is correct
44 Correct 17 ms 28936 KB Output is correct
45 Correct 141 ms 51368 KB Output is correct
46 Correct 124 ms 51308 KB Output is correct
47 Correct 104 ms 63404 KB Output is correct
48 Correct 45 ms 39688 KB Output is correct
49 Correct 37 ms 35608 KB Output is correct
50 Correct 32 ms 35460 KB Output is correct
51 Correct 64 ms 43728 KB Output is correct
52 Correct 73 ms 45036 KB Output is correct
53 Correct 31 ms 33288 KB Output is correct
54 Correct 17 ms 29896 KB Output is correct
55 Correct 21 ms 31060 KB Output is correct
56 Correct 24 ms 31188 KB Output is correct
57 Correct 61 ms 48844 KB Output is correct
58 Correct 25 ms 31828 KB Output is correct
59 Correct 29 ms 33344 KB Output is correct
60 Correct 33 ms 35200 KB Output is correct
61 Correct 31 ms 33876 KB Output is correct
62 Correct 85 ms 52292 KB Output is correct
63 Runtime error 159 ms 150032 KB Execution killed with signal 11
64 Halted 0 ms 0 KB -