#include <bits/stdc++.h>
#define ii pair<int, int>
#define fs first
#define sc second
using namespace std;
const int N = 1e5 + 1;
int n;
int can[11][N];
ii pa[11][N];
int res[N];
string grid[N];
void print(int x, int y) {
res[y] = x;
ii zero = {0, 0};
while (pa[x][y] != zero) {
ii tem = pa[x][y];
x = tem.fs, y = tem.sc;
res[y] = x;
}
queue<ii> ans;
int times = 0;
int start = -1, t = 0;
for (int i = 2; i < n; i++) {
if (res[i] <= res[i+1]) {
if (start == -1) start = i;
t++;
} else {
if (start == -1) continue;
ans.push({start, t});
start = -1, t = 0;
times++;
}
}
if (start != -1) {
ans.push({start, t});
times++;
}
cout << times << endl;
while (ans.size()) {
ii tem = ans.front(); ans.pop();
cout << tem.fs - 1 << " " << tem.sc << endl;
}
exit(0);
}
signed main() {
cin >> n;
for (int i = 10; i > 0; i--) {
string s; cin >> s;
s = "~" + s;
grid[i] = s;
}
can[1][2] = 1;
for (int c = 3; c <= n; c++) {
for (int r = 1; r <= 10; r++) {
if (grid[r][c] == 'X') {
continue;
}
if (r == 10) {
can[r][c] = can[r-1][c-1] || can[r][c-1];
if (can[r-1][c-1]) pa[r][c] = {r-1, c-1};
else if (can[r][c-1]) pa[r][c] = {r, c-1};
} else if (r == 1) {
can[r][c] = can[r+1][c-1] || can[r][c-1];
if (can[r+1][c-1]) pa[r][c] = {r+1, c-1};
else if (can[r][c-1]) pa[r][c] = {r, c-1};
} else {
can[r][c] = can[r+1][c-1] || can[r-1][c-1];
if (can[r+1][c-1]) pa[r][c] = {r+1, c-1};
else if (can[r-1][c-1]) pa[r][c] = {r-1, c-1};
}
}
}
for (int i = 10; i > 0; i--) {
if (can[i][n]) print(i, n);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3540 KB |
Crashed with an obstacle |
| 2 |
Incorrect |
2 ms |
3440 KB |
Crashed with an obstacle |
| 3 |
Incorrect |
2 ms |
3540 KB |
Crashed with an obstacle |
| 4 |
Incorrect |
3 ms |
3668 KB |
Crashed with an obstacle |
| 5 |
Incorrect |
6 ms |
4180 KB |
Crashed with an obstacle |
| 6 |
Incorrect |
7 ms |
4436 KB |
Crashed with an obstacle |
| 7 |
Incorrect |
16 ms |
6268 KB |
Crashed with an obstacle |
| 8 |
Incorrect |
40 ms |
10476 KB |
Crashed with an obstacle |
| 9 |
Incorrect |
52 ms |
13924 KB |
Crashed with an obstacle |
| 10 |
Incorrect |
71 ms |
17868 KB |
Crashed with an obstacle |
