oj.uz

Submission #472049

# Submission time Handle Problem Language Result Execution time Memory
472049 2021-09-12T13:48:10 Z hhhhaura Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 170 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 = 5000000;
	const int K = 180;
	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:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     while(id + 1 < v.size() && v[id + 1] <= k) id ++;
      |           ~~~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 255044 KB Output is correct
2 Correct 155 ms 255032 KB Output is correct
3 Correct 157 ms 255056 KB Output is correct
4 Correct 154 ms 254968 KB Output is correct
5 Correct 152 ms 255024 KB Output is correct
6 Correct 156 ms 255064 KB Output is correct
7 Correct 162 ms 255200 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 255032 KB Output is correct
2 Correct 169 ms 254988 KB Output is correct
3 Correct 159 ms 255028 KB Output is correct
4 Correct 151 ms 255044 KB Output is correct
5 Correct 152 ms 255060 KB Output is correct
6 Correct 151 ms 254972 KB Output is correct
7 Correct 161 ms 255072 KB Output is correct
8 Correct 153 ms 255100 KB Output is correct
9 Correct 159 ms 254976 KB Output is correct
10 Correct 155 ms 255096 KB Output is correct
11 Correct 154 ms 255360 KB Output is correct
12 Correct 155 ms 255008 KB Output is correct
13 Correct 155 ms 255036 KB Output is correct
14 Correct 157 ms 255436 KB Output is correct
15 Correct 161 ms 255428 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 255044 KB Output is correct
2 Correct 151 ms 255044 KB Output is correct
3 Correct 152 ms 255044 KB Output is correct
4 Correct 152 ms 255028 KB Output is correct
5 Correct 156 ms 255044 KB Output is correct
6 Correct 157 ms 255168 KB Output is correct
7 Correct 154 ms 254984 KB Output is correct
8 Correct 156 ms 255112 KB Output is correct
9 Correct 153 ms 255124 KB Output is correct
10 Correct 154 ms 255196 KB Output is correct
11 Correct 153 ms 255300 KB Output is correct
12 Correct 152 ms 255104 KB Output is correct
13 Correct 152 ms 255044 KB Output is correct
14 Correct 155 ms 255476 KB Output is correct
15 Correct 156 ms 255544 KB Output is correct
16 Correct 154 ms 255292 KB Output is correct
17 Correct 157 ms 255980 KB Output is correct
18 Correct 155 ms 255452 KB Output is correct
19 Correct 160 ms 255428 KB Output is correct
20 Correct 158 ms 255284 KB Output is correct
21 Correct 153 ms 255196 KB Output is correct
22 Correct 159 ms 255388 KB Output is correct
23 Correct 160 ms 255604 KB Output is correct
24 Correct 159 ms 255832 KB Output is correct
25 Correct 156 ms 255468 KB Output is correct
26 Correct 161 ms 255592 KB Output is correct
27 Correct 156 ms 255496 KB Output is correct
28 Correct 161 ms 256460 KB Output is correct
29 Correct 170 ms 258848 KB Output is correct
30 Correct 156 ms 256124 KB Output is correct
31 Correct 160 ms 257092 KB Output is correct
32 Correct 160 ms 256480 KB Output is correct
33 Runtime error 151 ms 262148 KB Execution killed with signal 9
34 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 254988 KB Output is correct
2 Correct 154 ms 255044 KB Output is correct
3 Correct 156 ms 255004 KB Output is correct
4 Correct 151 ms 255012 KB Output is correct
5 Correct 157 ms 255100 KB Output is correct
6 Correct 153 ms 255076 KB Output is correct
7 Correct 152 ms 255044 KB Output is correct
8 Correct 158 ms 254988 KB Output is correct
9 Correct 158 ms 255132 KB Output is correct
10 Correct 157 ms 255172 KB Output is correct
11 Correct 155 ms 255308 KB Output is correct
12 Correct 154 ms 255044 KB Output is correct
13 Correct 154 ms 255100 KB Output is correct
14 Correct 159 ms 255428 KB Output is correct
15 Correct 159 ms 255420 KB Output is correct
16 Correct 155 ms 255324 KB Output is correct
17 Correct 159 ms 255992 KB Output is correct
18 Correct 153 ms 255416 KB Output is correct
19 Correct 154 ms 255384 KB Output is correct
20 Correct 159 ms 255340 KB Output is correct
21 Correct 154 ms 255172 KB Output is correct
22 Correct 155 ms 255396 KB Output is correct
23 Correct 157 ms 255500 KB Output is correct
24 Correct 160 ms 255832 KB Output is correct
25 Correct 159 ms 255588 KB Output is correct
26 Correct 160 ms 255556 KB Output is correct
27 Correct 157 ms 255464 KB Output is correct
28 Correct 164 ms 256664 KB Output is correct
29 Correct 166 ms 258952 KB Output is correct
30 Correct 163 ms 256164 KB Output is correct
31 Correct 162 ms 257204 KB Output is correct
32 Correct 161 ms 256652 KB Output is correct
33 Runtime error 153 ms 262148 KB Execution killed with signal 9
34 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 255016 KB Output is correct
2 Correct 154 ms 255044 KB Output is correct
3 Correct 152 ms 255044 KB Output is correct
4 Correct 151 ms 255096 KB Output is correct
5 Correct 152 ms 255064 KB Output is correct
6 Correct 154 ms 255096 KB Output is correct
7 Correct 158 ms 255032 KB Output is correct
8 Correct 155 ms 255080 KB Output is correct
9 Correct 157 ms 255048 KB Output is correct
10 Correct 153 ms 255176 KB Output is correct
11 Correct 158 ms 255360 KB Output is correct
12 Correct 160 ms 255072 KB Output is correct
13 Correct 156 ms 255024 KB Output is correct
14 Correct 159 ms 255660 KB Output is correct
15 Correct 157 ms 255508 KB Output is correct
16 Correct 152 ms 255332 KB Output is correct
17 Correct 154 ms 256048 KB Output is correct
18 Correct 156 ms 255556 KB Output is correct
19 Correct 157 ms 255316 KB Output is correct
20 Correct 153 ms 255180 KB Output is correct
21 Correct 151 ms 255236 KB Output is correct
22 Correct 160 ms 255548 KB Output is correct
23 Correct 163 ms 255400 KB Output is correct
24 Correct 153 ms 255824 KB Output is correct
25 Correct 156 ms 255556 KB Output is correct
26 Correct 155 ms 255656 KB Output is correct
27 Correct 155 ms 255428 KB Output is correct
28 Correct 161 ms 256476 KB Output is correct
29 Correct 166 ms 258884 KB Output is correct
30 Correct 160 ms 256244 KB Output is correct
31 Correct 161 ms 257108 KB Output is correct
32 Correct 158 ms 256524 KB Output is correct
33 Runtime error 149 ms 262148 KB Execution killed with signal 9
34 Halted 0 ms 0 KB -