Submission #558815

#	Time	Username	Problem	Language	Result	Execution time	Memory
558815		hhhhaura	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	473 ms	96824 KiB

skyscraper

#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 = 175, mx = 8000000;
	vector<pii> a;
	vector<int> v[P + 1][P + 1];
	vector<vector<int>> to;
	vector<int> dis, yes, dir;
	void init_(int _n, int _m) {
		ii = _n;
		n = _n, m = _m;
		a.clear();
		to.assign(n, vector<int>());
		yes.assign(mx, 0);
		dir.assign(mx, 0);
		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 == i.y) to[j].push_back(ii);
				yes[ii] = j;
				dir[ii] = i.x;
			}
		}
		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(cur < v[i][j].size() && 
					v[i][j][cur] == k) to[k].push_back(ii), cur++;
				yes[ii] = k;
				dir[ii] = i;
			}
		}
		dis[s] = 0;
		deque<int> q;
		q.push_back(s);
		auto trans = [&](int a, int b, int c) {
			if(dis[b] != INF) return;
			dis[b] = dis[a] + c;
			if(c) q.push_back(b);
			else q.push_front(b);
		};
		while(q.size()) {
			int cur = q.front();
			q.pop_front();
			if(cur == t) {
				cout << dis[cur] << "\n";
				return;
			}
			if(cur < n) for(auto i : to[cur]) trans(cur, i, 0);
			else {
				if(yes[cur] - dir[cur] >= 0) trans(cur, cur - 1, 1);
				if(yes[cur] + dir[cur] < n) trans(cur, cur + 1, 1);
				trans(cur, yes[cur], 0);
			}
		}
		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 (stderr)

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:60:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     if(cur < v[i][j].size() &&
      |        ~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 43 / 43