#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> baris[30005];
int n, m, tujuan, ans = INT_MAX;
void solve(int pos, int p, int count) {
// cout << pos << " " << p << " " << count << endl;
// return 0;
if (pos == tujuan) {
ans = min(count, ans);
return;
}
// while (pos >= 0 and pos < n) {
// if (pos < 0 or pos >= n) return;
// if (pos-p >= 0) solve(pos-p, p, count+1);
// if (pos+p < n) solve(pos+p, p, count+1);
int cur = pos;
int temp = 0;
while (cur-p >= 0) {
cur -= p;
temp += 1;
// cout << "cur " << cur << endl;
if (!baris[cur].empty()) {
// cout << "NOT EMPTY" << endl;
for (int i = 0; i < baris[cur].size(); i++) {
int save = baris[cur][i];
baris[cur].erase(baris[cur].begin()+i);
solve(cur, save, count+temp);
baris[cur].push_back(save);
}
}
}
cur = pos;
temp = 0;
while (cur+p < n) {
cur += p;
temp += 1;
// cout << "cur " << cur << endl;
if (!baris[cur].empty()) {
// cout << "NOT EMPTY" << endl;
for (int i = 0; i < baris[cur].size(); i++) {
int save = baris[cur][i];
baris[cur].erase(baris[cur].begin()+i);
solve(cur, save, count+temp);
baris[cur].push_back(save);
}
}
}
// }
}
signed main() {
int b, p, posstart, pstart;
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> b >> p;
if (i == 0) {
posstart = b;
pstart = p;
} else {
if (i == 1) tujuan = b;
// cout << b << endl;
baris[b].push_back(p);
}
}
solve(posstart, pstart, 0);
if (ans == INT_MAX) cout << -1 << endl;
else cout << ans << endl;
// vector<int> a;
// a.push_back(1);
// a.push_back(2);
// for (auto i: a) cout << i << " ";
// cout << endl;
// a.erase(a.begin()+1);
// for (auto i: a) cout << i << " ";
// cout << endl;
}
Compilation message
skyscraper.cpp: In function 'void solve(long long int, long long int, long long int)':
skyscraper.cpp:30:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for (int i = 0; i < baris[cur].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~~
skyscraper.cpp:47:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for (int i = 0; i < baris[cur].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~~
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:74:8: warning: 'pstart' may be used uninitialized in this function [-Wmaybe-uninitialized]
74 | solve(posstart, pstart, 0);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:74:8: warning: 'posstart' may be used uninitialized in this function [-Wmaybe-uninitialized]
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
1 ms |
980 KB |
Output is correct |
6 |
Correct |
1 ms |
980 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
1 ms |
980 KB |
Output is correct |
6 |
Correct |
1 ms |
980 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
980 KB |
Output is correct |
9 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
1 ms |
980 KB |
Output is correct |
6 |
Correct |
1 ms |
980 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
980 KB |
Output is correct |
9 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
1 ms |
980 KB |
Output is correct |
6 |
Correct |
1 ms |
980 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
980 KB |
Output is correct |
9 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
1 ms |
980 KB |
Output is correct |
6 |
Correct |
1 ms |
980 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
980 KB |
Output is correct |
9 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |