# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
245688 | Vladikus004 | Jetpack (COCI16_jetpack) | C++14 | 18 ms | 5888 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define inf 2e9
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
const int N = 100000 + 3;
int n, can[10][N];
char a[10][N];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif // LOCAL
cin >> n;
for (int i = 0; i < 10; i++)
cin >> a[i];
can[9][0] = 1;
for (int j = 1; j < n; j++){
for (int i = 0; i < 10; i++){
if (a[i][j] == 'X') continue;
int x1, y1, x2, y2;
x1 = i - 1; y1 = j - 1;
x2 = i + 1; y2 = j - 1;
x1 = max(x1, 0);
x2 = min(x2, 9);
can[i][j] = max(can[x1][y1], can[x2][y2]);
}
}
// for (int i = 0; i < 10; i++){
// for (int j = 0; j < n; j++){
// cout << can[i][j];
// }
// cout << '\n';
// }
int x;
for (int i = 0; i < 10; i++)
if (can[i][n - 1]){
x = i;
}
vector <int> way;
int last = 0;
int j = n - 1;
while (j){
int x1, y1, x2, y2;
x1 = x - 1; y1 = j - 1;
x2 = x + 1; y2 = j - 1;
--j;
x1 = max(x1, 0);
x2 = min(x2, 9);
if (x == 9){
way.push_back(0);
if (!can[x2][y2]) x = 8;
last = 0;
continue;
}
if (x == 0){
way.push_back(1);
if (!can[x1][y1]) x = 1;
last = 1;
continue;
}
if (!last){
if (can[x1][y1]) way.push_back(0);
else way.push_back(1);
}else{
if (can[x2][y2]) way.push_back(1);
else way.push_back(0);
}
last = way.back();
if (last) x = min(x + 1, 9);
else x = max(x - 1, 0);
}
reverse(all(way));
// for (auto u: way) cout << u << " "; cout << "!\n";
vector <pii> ans;
int st = 0, sum = 0;
last = 0;
for (int i = 0; i < way.size(); i++){
if (way[i] && last == 0){
st = i;
sum = 1;
}else
if (way[i] && last){
sum++;
}else
if (!way[i] && last){
ans.push_back({st, sum});
}
last = way[i];
}
cout << ans.size() << "\n";
for (auto u: ans) cout << u.first << " " << u.second << "\n";
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |