oj.uz

Submission #472051

# Submission time Handle Problem Language Result Execution time Memory
472051 2021-09-12T13:53:09 Z hhhhaura Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 336 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 = 6000000;
	const int K = 174;
	int n, m, st, ed, ii;
	vector<int> dis, s;
	vector<vector<pair<int, bool>>> 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<pair<int, bool>>());
		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) 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);
				if(i.first == ed) return dis[ed];
			}
		}
		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 93 ms 164976 KB Output is correct
2 Correct 92 ms 164940 KB Output is correct
3 Correct 93 ms 164948 KB Output is correct
4 Correct 93 ms 165052 KB Output is correct
5 Correct 90 ms 165008 KB Output is correct
6 Correct 93 ms 165056 KB Output is correct
7 Correct 96 ms 165036 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 164988 KB Output is correct
2 Correct 93 ms 164988 KB Output is correct
3 Correct 90 ms 164980 KB Output is correct
4 Correct 92 ms 164980 KB Output is correct
5 Correct 95 ms 165016 KB Output is correct
6 Correct 91 ms 164932 KB Output is correct
7 Correct 95 ms 165048 KB Output is correct
8 Correct 95 ms 165032 KB Output is correct
9 Correct 95 ms 165012 KB Output is correct
10 Correct 90 ms 165100 KB Output is correct
11 Correct 90 ms 165292 KB Output is correct
12 Correct 90 ms 165072 KB Output is correct
13 Correct 89 ms 165060 KB Output is correct
14 Correct 100 ms 165356 KB Output is correct
15 Correct 94 ms 165264 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 165004 KB Output is correct
2 Correct 89 ms 164952 KB Output is correct
3 Correct 90 ms 165060 KB Output is correct
4 Correct 89 ms 164984 KB Output is correct
5 Correct 88 ms 164964 KB Output is correct
6 Correct 88 ms 164932 KB Output is correct
7 Correct 91 ms 165056 KB Output is correct
8 Correct 95 ms 165048 KB Output is correct
9 Correct 92 ms 165008 KB Output is correct
10 Correct 90 ms 165060 KB Output is correct
11 Correct 92 ms 165260 KB Output is correct
12 Correct 100 ms 165056 KB Output is correct
13 Correct 92 ms 164952 KB Output is correct
14 Correct 90 ms 165360 KB Output is correct
15 Correct 95 ms 165348 KB Output is correct
16 Correct 89 ms 165212 KB Output is correct
17 Correct 93 ms 165624 KB Output is correct
18 Correct 102 ms 165260 KB Output is correct
19 Correct 94 ms 165276 KB Output is correct
20 Correct 92 ms 165196 KB Output is correct
21 Correct 91 ms 165096 KB Output is correct
22 Correct 91 ms 165276 KB Output is correct
23 Correct 92 ms 165364 KB Output is correct
24 Correct 95 ms 165560 KB Output is correct
25 Correct 90 ms 165332 KB Output is correct
26 Correct 91 ms 165424 KB Output is correct
27 Correct 95 ms 165364 KB Output is correct
28 Correct 95 ms 166212 KB Output is correct
29 Correct 101 ms 167904 KB Output is correct
30 Correct 97 ms 165856 KB Output is correct
31 Correct 98 ms 166568 KB Output is correct
32 Correct 94 ms 166056 KB Output is correct
33 Correct 127 ms 170652 KB Output is correct
34 Correct 118 ms 170640 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 164996 KB Output is correct
2 Correct 97 ms 165060 KB Output is correct
3 Correct 91 ms 165060 KB Output is correct
4 Correct 91 ms 165004 KB Output is correct
5 Correct 89 ms 165040 KB Output is correct
6 Correct 91 ms 164932 KB Output is correct
7 Correct 92 ms 164968 KB Output is correct
8 Correct 92 ms 164976 KB Output is correct
9 Correct 89 ms 165060 KB Output is correct
10 Correct 93 ms 165256 KB Output is correct
11 Correct 92 ms 165188 KB Output is correct
12 Correct 91 ms 165020 KB Output is correct
13 Correct 96 ms 165048 KB Output is correct
14 Correct 95 ms 165252 KB Output is correct
15 Correct 89 ms 165316 KB Output is correct
16 Correct 90 ms 165244 KB Output is correct
17 Correct 95 ms 165680 KB Output is correct
18 Correct 91 ms 165316 KB Output is correct
19 Correct 93 ms 165204 KB Output is correct
20 Correct 93 ms 165116 KB Output is correct
21 Correct 92 ms 165052 KB Output is correct
22 Correct 100 ms 165240 KB Output is correct
23 Correct 94 ms 165344 KB Output is correct
24 Correct 98 ms 165572 KB Output is correct
25 Correct 93 ms 165300 KB Output is correct
26 Correct 100 ms 165348 KB Output is correct
27 Correct 93 ms 165316 KB Output is correct
28 Correct 95 ms 166044 KB Output is correct
29 Correct 112 ms 167896 KB Output is correct
30 Correct 93 ms 165784 KB Output is correct
31 Correct 100 ms 166592 KB Output is correct
32 Correct 94 ms 166176 KB Output is correct
33 Correct 133 ms 170720 KB Output is correct
34 Correct 116 ms 170616 KB Output is correct
35 Correct 114 ms 169668 KB Output is correct
36 Correct 95 ms 165956 KB Output is correct
37 Correct 123 ms 173032 KB Output is correct
38 Correct 123 ms 172264 KB Output is correct
39 Correct 121 ms 172216 KB Output is correct
40 Correct 125 ms 172300 KB Output is correct
41 Correct 121 ms 172232 KB Output is correct
42 Correct 96 ms 165440 KB Output is correct
43 Correct 96 ms 165424 KB Output is correct
44 Correct 100 ms 165304 KB Output is correct
45 Correct 247 ms 187716 KB Output is correct
46 Correct 221 ms 187624 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 164932 KB Output is correct
2 Correct 94 ms 165028 KB Output is correct
3 Correct 94 ms 164972 KB Output is correct
4 Correct 90 ms 165008 KB Output is correct
5 Correct 91 ms 165052 KB Output is correct
6 Correct 93 ms 165020 KB Output is correct
7 Correct 92 ms 165064 KB Output is correct
8 Correct 99 ms 164952 KB Output is correct
9 Correct 90 ms 164972 KB Output is correct
10 Correct 91 ms 165056 KB Output is correct
11 Correct 95 ms 165188 KB Output is correct
12 Correct 92 ms 165076 KB Output is correct
13 Correct 103 ms 165008 KB Output is correct
14 Correct 98 ms 165264 KB Output is correct
15 Correct 92 ms 165368 KB Output is correct
16 Correct 91 ms 165188 KB Output is correct
17 Correct 93 ms 165660 KB Output is correct
18 Correct 92 ms 165320 KB Output is correct
19 Correct 95 ms 165204 KB Output is correct
20 Correct 92 ms 165188 KB Output is correct
21 Correct 91 ms 165116 KB Output is correct
22 Correct 92 ms 165316 KB Output is correct
23 Correct 96 ms 165360 KB Output is correct
24 Correct 96 ms 165596 KB Output is correct
25 Correct 93 ms 165300 KB Output is correct
26 Correct 98 ms 165432 KB Output is correct
27 Correct 93 ms 165296 KB Output is correct
28 Correct 94 ms 166084 KB Output is correct
29 Correct 101 ms 167876 KB Output is correct
30 Correct 98 ms 165772 KB Output is correct
31 Correct 100 ms 166600 KB Output is correct
32 Correct 97 ms 166152 KB Output is correct
33 Correct 118 ms 170688 KB Output is correct
34 Correct 114 ms 170692 KB Output is correct
35 Correct 113 ms 169644 KB Output is correct
36 Correct 95 ms 165876 KB Output is correct
37 Correct 122 ms 172996 KB Output is correct
38 Correct 129 ms 172356 KB Output is correct
39 Correct 120 ms 172384 KB Output is correct
40 Correct 118 ms 172308 KB Output is correct
41 Correct 121 ms 172228 KB Output is correct
42 Correct 100 ms 165492 KB Output is correct
43 Correct 110 ms 165444 KB Output is correct
44 Correct 95 ms 165244 KB Output is correct
45 Correct 242 ms 187740 KB Output is correct
46 Correct 222 ms 187624 KB Output is correct
47 Correct 206 ms 199456 KB Output is correct
48 Correct 129 ms 175872 KB Output is correct
49 Correct 118 ms 171668 KB Output is correct
50 Correct 115 ms 171728 KB Output is correct
51 Correct 154 ms 179780 KB Output is correct
52 Correct 157 ms 181060 KB Output is correct
53 Correct 114 ms 169284 KB Output is correct
54 Correct 95 ms 166424 KB Output is correct
55 Correct 104 ms 167592 KB Output is correct
56 Correct 103 ms 167492 KB Output is correct
57 Correct 152 ms 185340 KB Output is correct
58 Correct 107 ms 168316 KB Output is correct
59 Correct 118 ms 169668 KB Output is correct
60 Correct 125 ms 171504 KB Output is correct
61 Correct 112 ms 170200 KB Output is correct
62 Correct 187 ms 188356 KB Output is correct
63 Runtime error 336 ms 262148 KB Execution killed with signal 9
64 Halted 0 ms 0 KB -