oj.uz

Submission #472039

# Submission time Handle Problem Language Result Execution time Memory
472039 2021-09-12T13:27:40 Z hhhhaura Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 320 ms 262148 KB 
#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 = 7000000;
	const int K = 200;
	int n, m, st, ed, ii;
	vector<int> dis, s;
	vector<vector<pii>> mp;
	vector<vector<vector<int>>> a;
	void init_(int _n, int _m) {
		n = _n, m = _m, ii = n - 1;
		s.clear();
		dis.assign(P, INF);
		mp.assign(P, vector<pii>());
		a.assign(K, vector<vector<int>>(K, vector<int>()));
	}
	void get_new() {
		ii++;
		if(ii >= P) while(1);
	}
	void add_node(int pos, int b) {
		for(int i = pos % b; i < n; i += b) {
			get_new();
			if(i == pos) mp[i].push_back({ii, 0});
			if(i != pos % b) {
				mp[ii].push_back({ii - 1, 1});
				mp[ii - 1].push_back({ii, 1});
			}
			mp[ii].push_back({i, 0});
		}
	}
	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) mp[k].push_back({ii, 0});
				if(k != j) {
					mp[ii].push_back({ii - 1, 1});
					mp[ii - 1].push_back({ii, 1});
				}
				mp[ii].push_back({k, 0});
			}
		}
		dis[st] = 0;
		deque<int> q;
		q.push_back(st);
		while(q.size()) {
			int cur = q.front();
			q.pop_front();
			for(auto i : mp[cur]) if(dis[i.first] == INF) {
				dis[i.first] = i.second + dis[cur];
				if(i.second) q.push_back(i.first);
				else q.push_front(i.first);
			}
		}
		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:67:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     while(id + 1 < v.size() && v[id + 1] <= k) id ++;
      |           ~~~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 193016 KB Output is correct
2 Correct 107 ms 193020 KB Output is correct
3 Correct 105 ms 192992 KB Output is correct
4 Correct 103 ms 192948 KB Output is correct
5 Correct 104 ms 192912 KB Output is correct
6 Correct 106 ms 193032 KB Output is correct
7 Correct 105 ms 192968 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 193020 KB Output is correct
2 Correct 104 ms 192988 KB Output is correct
3 Correct 108 ms 193000 KB Output is correct
4 Correct 103 ms 192968 KB Output is correct
5 Correct 103 ms 192968 KB Output is correct
6 Correct 102 ms 193036 KB Output is correct
7 Correct 103 ms 193004 KB Output is correct
8 Correct 112 ms 193028 KB Output is correct
9 Correct 110 ms 193092 KB Output is correct
10 Correct 104 ms 193044 KB Output is correct
11 Correct 110 ms 193152 KB Output is correct
12 Correct 103 ms 192988 KB Output is correct
13 Correct 105 ms 193016 KB Output is correct
14 Correct 110 ms 193332 KB Output is correct
15 Correct 119 ms 193348 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 192984 KB Output is correct
2 Correct 104 ms 192960 KB Output is correct
3 Correct 108 ms 193032 KB Output is correct
4 Correct 104 ms 192972 KB Output is correct
5 Correct 102 ms 193036 KB Output is correct
6 Correct 103 ms 192964 KB Output is correct
7 Correct 102 ms 193012 KB Output is correct
8 Correct 104 ms 193080 KB Output is correct
9 Correct 104 ms 193036 KB Output is correct
10 Correct 117 ms 193016 KB Output is correct
11 Correct 113 ms 193264 KB Output is correct
12 Correct 104 ms 192964 KB Output is correct
13 Correct 107 ms 192968 KB Output is correct
14 Correct 103 ms 193328 KB Output is correct
15 Correct 116 ms 193332 KB Output is correct
16 Correct 104 ms 193108 KB Output is correct
17 Correct 108 ms 193604 KB Output is correct
18 Correct 106 ms 193352 KB Output is correct
19 Correct 106 ms 193136 KB Output is correct
20 Correct 106 ms 193204 KB Output is correct
21 Correct 104 ms 193092 KB Output is correct
22 Correct 104 ms 193296 KB Output is correct
23 Correct 114 ms 193276 KB Output is correct
24 Correct 110 ms 193620 KB Output is correct
25 Correct 103 ms 193360 KB Output is correct
26 Correct 105 ms 193312 KB Output is correct
27 Correct 106 ms 193368 KB Output is correct
28 Correct 110 ms 194256 KB Output is correct
29 Correct 113 ms 195828 KB Output is correct
30 Correct 107 ms 193756 KB Output is correct
31 Correct 108 ms 194492 KB Output is correct
32 Correct 110 ms 194048 KB Output is correct
33 Correct 129 ms 198744 KB Output is correct
34 Correct 134 ms 198644 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 192940 KB Output is correct
2 Correct 107 ms 192964 KB Output is correct
3 Correct 109 ms 193016 KB Output is correct
4 Correct 104 ms 192940 KB Output is correct
5 Correct 101 ms 192964 KB Output is correct
6 Correct 104 ms 193016 KB Output is correct
7 Correct 103 ms 192944 KB Output is correct
8 Correct 106 ms 192948 KB Output is correct
9 Correct 110 ms 193044 KB Output is correct
10 Correct 103 ms 193008 KB Output is correct
11 Correct 105 ms 193348 KB Output is correct
12 Correct 104 ms 193012 KB Output is correct
13 Correct 108 ms 193044 KB Output is correct
14 Correct 118 ms 193348 KB Output is correct
15 Correct 103 ms 193276 KB Output is correct
16 Correct 103 ms 193168 KB Output is correct
17 Correct 114 ms 193604 KB Output is correct
18 Correct 111 ms 193368 KB Output is correct
19 Correct 106 ms 193176 KB Output is correct
20 Correct 107 ms 193088 KB Output is correct
21 Correct 119 ms 193036 KB Output is correct
22 Correct 107 ms 193308 KB Output is correct
23 Correct 102 ms 193432 KB Output is correct
24 Correct 108 ms 193560 KB Output is correct
25 Correct 104 ms 193348 KB Output is correct
26 Correct 105 ms 193344 KB Output is correct
27 Correct 104 ms 193328 KB Output is correct
28 Correct 109 ms 194008 KB Output is correct
29 Correct 115 ms 195896 KB Output is correct
30 Correct 110 ms 193752 KB Output is correct
31 Correct 110 ms 194480 KB Output is correct
32 Correct 106 ms 194168 KB Output is correct
33 Correct 124 ms 198596 KB Output is correct
34 Correct 125 ms 198680 KB Output is correct
35 Correct 130 ms 197700 KB Output is correct
36 Correct 109 ms 193736 KB Output is correct
37 Correct 153 ms 201044 KB Output is correct
38 Correct 149 ms 200332 KB Output is correct
39 Correct 149 ms 200300 KB Output is correct
40 Correct 149 ms 200336 KB Output is correct
41 Correct 152 ms 200460 KB Output is correct
42 Correct 124 ms 193412 KB Output is correct
43 Correct 111 ms 193452 KB Output is correct
44 Correct 111 ms 193356 KB Output is correct
45 Correct 255 ms 215716 KB Output is correct
46 Correct 243 ms 215700 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 193016 KB Output is correct
2 Correct 105 ms 192960 KB Output is correct
3 Correct 115 ms 192976 KB Output is correct
4 Correct 106 ms 192988 KB Output is correct
5 Correct 103 ms 192964 KB Output is correct
6 Correct 108 ms 192964 KB Output is correct
7 Correct 104 ms 192996 KB Output is correct
8 Correct 103 ms 192992 KB Output is correct
9 Correct 105 ms 193024 KB Output is correct
10 Correct 107 ms 193108 KB Output is correct
11 Correct 104 ms 193220 KB Output is correct
12 Correct 104 ms 193036 KB Output is correct
13 Correct 105 ms 192936 KB Output is correct
14 Correct 104 ms 193348 KB Output is correct
15 Correct 117 ms 193348 KB Output is correct
16 Correct 102 ms 193220 KB Output is correct
17 Correct 110 ms 193716 KB Output is correct
18 Correct 107 ms 193288 KB Output is correct
19 Correct 106 ms 193200 KB Output is correct
20 Correct 105 ms 193152 KB Output is correct
21 Correct 103 ms 193044 KB Output is correct
22 Correct 105 ms 193228 KB Output is correct
23 Correct 121 ms 193304 KB Output is correct
24 Correct 109 ms 193512 KB Output is correct
25 Correct 107 ms 193292 KB Output is correct
26 Correct 122 ms 193308 KB Output is correct
27 Correct 106 ms 193304 KB Output is correct
28 Correct 109 ms 194068 KB Output is correct
29 Correct 121 ms 195872 KB Output is correct
30 Correct 108 ms 193752 KB Output is correct
31 Correct 114 ms 194604 KB Output is correct
32 Correct 118 ms 194152 KB Output is correct
33 Correct 132 ms 198656 KB Output is correct
34 Correct 135 ms 198700 KB Output is correct
35 Correct 137 ms 197872 KB Output is correct
36 Correct 120 ms 193792 KB Output is correct
37 Correct 189 ms 201140 KB Output is correct
38 Correct 152 ms 200648 KB Output is correct
39 Correct 156 ms 200556 KB Output is correct
40 Correct 179 ms 200596 KB Output is correct
41 Correct 157 ms 200612 KB Output is correct
42 Correct 112 ms 193608 KB Output is correct
43 Correct 129 ms 193600 KB Output is correct
44 Correct 111 ms 193604 KB Output is correct
45 Correct 255 ms 216232 KB Output is correct
46 Correct 253 ms 215876 KB Output is correct
47 Correct 320 ms 227824 KB Output is correct
48 Correct 144 ms 204168 KB Output is correct
49 Correct 132 ms 199948 KB Output is correct
50 Correct 132 ms 199896 KB Output is correct
51 Correct 188 ms 208196 KB Output is correct
52 Correct 203 ms 209452 KB Output is correct
53 Correct 149 ms 197596 KB Output is correct
54 Correct 110 ms 194336 KB Output is correct
55 Correct 125 ms 195584 KB Output is correct
56 Correct 141 ms 195780 KB Output is correct
57 Correct 244 ms 213448 KB Output is correct
58 Correct 123 ms 196408 KB Output is correct
59 Correct 143 ms 197912 KB Output is correct
60 Correct 138 ms 199616 KB Output is correct
61 Correct 137 ms 198368 KB Output is correct
62 Correct 193 ms 216600 KB Output is correct
63 Runtime error 270 ms 262148 KB Execution killed with signal 9
64 Halted 0 ms 0 KB -