#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
int dp[30001];
vector<int> G[30001];
int A[30001][2];
int l[30001], r[30001];
vector<pii> H[30001];
vector<int> q[30001];
int main(){
int n, k;
cin >> n >> k;
set<pii> M;
for(int i = 0; i < k; i++){
cin >> A[i][0] >> A[i][1];
if(i >= 2 && M.count({A[i][0], A[i][1]})){
continue;
}
M.insert({A[i][0], A[i][1]});
G[A[i][0]].push_back(i);
H[A[i][1]].push_back({A[i][0], i});
}
for(int i = 1; i <= 30000; i++){
sort(H[i].begin(), H[i].end(), [&i](pii aa, pii bb){
int a = aa.fi, b = bb.fi;
return a % i < b % i || a % i == b % i && a < b;
});
if(H[i].size() == 0) continue;
l[H[i].front().se] = H[i].front().fi % i;
for(int j = 0; j + 1 < H[i].size(); j++){
if(H[i][j].fi % i == H[i][j + 1].fi % i){
r[H[i][j].se] = H[i][j + 1].fi;
l[H[i][j + 1].se] = H[i][j].fi;
}else{
r[H[i][j].se] = n - 1;
l[H[i][j + 1].se] = H[i][j + 1].fi % i;
}
}
r[H[i].back().se] = n - 1;
}
// for(int i = 0; i < k; i++){
// cout << l[i] << ' ' << r[i] << endl;
// }
q[0].push_back(A[0][0]);
fill(dp, dp + n, 1 << 30);
for(int a = 0; a <= 30000; a++){
while(q[a].size()){
int v = q[a].back(); q[a].pop_back();
if(dp[v] != (1 << 30)) continue;
dp[v] = a;
for(auto i : G[v]){
for(int j = l[i]; j <= r[i]; j += A[i][1]){
int d = abs(v - j) / A[i][1];
if(dp[j] > a + d && a + d < n) q[a + d].push_back(j);
}
}
}
}
cout << (dp[A[1][0]] == (1 << 30) ? -1 : dp[A[1][0]]) << endl;
}
Compilation message
skyscraper.cpp: In lambda function:
skyscraper.cpp:29:43: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
29 | return a % i < b % i || a % i == b % i && a < b;
| ~~~~~~~~~~~~~~~^~~~~~~~
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:33:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for(int j = 0; j + 1 < H[i].size(); j++){
| ~~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
