Submission #558814

#TimeUsernameProblemLanguageResultExecution timeMemory
558814hhhhauraJakarta Skyscrapers (APIO15_skyscraper)C++14
57 / 100
230 ms262144 KiB
#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 = 200, mx = 8000000; 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 (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: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() &&
      |        ~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...