# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
300018 | shrek12357 | Jetpack (COCI16_jetpack) | C++14 | 6 ms | 512 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 <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <fstream>
#include <queue>
using namespace std;
const int MAXN = 50;
const int MAXVAL = 5 * 1e4;
struct state {
int row;
int col;
vector<pair<int, int>> moves;
};
int main() {
int n;
cin >> n;
bool dp[15][MAXN];
char grid[15][MAXN];
for (int i = 0; i < 10; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = false;
char temp;
cin >> temp;
grid[i][j] = temp;
}
}
dp[9][0] = true;
//queue<state> q;
int x = -1, y = -1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < 10; j++) {
if (grid[j][i] == 'X') {
continue;
}
if (j == 0) {
dp[j][i] = (dp[j][i - 1]) || (dp[j + 1][i - 1]);
}
else if (j == 9) {
dp[j][i] = (dp[j][i - 1]) || (dp[j - 1][i - 1]);
}
else {
dp[j][i] = (dp[j - 1][i - 1]) || (dp[j + 1][i - 1]);
}
if (i == n - 1 && dp[j][i]) {
//vector<pair<int, int>> temp;
//temp.push_back({ -1, 0 });
//q.push({ j, i, temp });
x = j;
y = i;
}
}
}
vector<pair<int, int>> ans;
/*
while (q.size() > 0) {
int curRow = q.front().row, curCol = q.front().col;
vector<pair<int, int>> curMoves = q.front().moves;
vector<pair<int, int>> temp1 = curMoves, temp2 = curMoves;
q.pop();
if (curCol == 0 && curMoves.size() <= MAXVAL) {
ans = curMoves;
break;
}
if (curRow == 0) {
if (dp[curRow][curCol - 1]) {
if (curMoves[curMoves.size() - 1].first == -1) {
temp1[temp1.size() - 1].first = curCol;
}
temp1[temp1.size() - 1].second++;
q.push({ curRow, curCol - 1, temp1 });
}
if (dp[curRow + 1][curCol - 1]) {
if (temp2[temp2.size() - 1].first == -1) {
temp2[temp2.size() - 1].first = curCol - 1;
}
temp2[temp2.size() - 1].second++;
q.push({ curRow + 1, curCol - 1, temp2 });
}
}
else if (curRow == 9) {
if (dp[curRow][curCol - 1]) {
if (curMoves[curMoves.size() - 1].first != -1) {
temp1.push_back({ -1, 0 });
}
q.push({ curRow, curCol - 1, temp1 });
}
if (dp[curRow - 1][curCol - 1]) {
if (curMoves[curMoves.size() - 1].first != -1) {
temp2.push_back({ -1, 0 });
}
q.push({ curRow, curCol - 1, temp2 });
}
}
else {
if (dp[curRow - 1][curCol - 1]) {
if (curMoves[curMoves.size() - 1].first != -1) {
temp1.push_back({ -1, 0 });
}
q.push({ curRow - 1, curCol - 1, temp1 });
}
if (dp[curRow + 1][curCol - 1]) {
if (curMoves[curMoves.size() - 1].first == -1) {
temp2[temp2.size() - 1].first = curCol - 1;
}
temp2[temp2.size() - 1].second++;
q.push({ curRow + 1, curCol - 1, temp2 });
}
}
}
*/
//cout << x << " " << y << endl;
int amnt = 0;
while (y != 0) {
if (x == 0) {
if (dp[x][y - 1]) {
y--;
amnt++;
}
else {
x++;
y--;
amnt++;
}
}
else if (x == 9) {
if (dp[x][y - 1]) {
if (amnt > 0) {
ans.push_back({ y, amnt });
}
amnt = 0;
y--;
}
else {
x--;
if (amnt > 0) {
ans.push_back({ y, amnt });
}
amnt = 0;
y--;
}
}
else {
if (dp[x - 1][y - 1]) {
if (amnt > 0) {
ans.push_back({ y, amnt });
}
amnt = 0;
x--;
y--;
}
else {
amnt++;
y--;
x++;
}
}
}
if (amnt > 0) {
ans.push_back({ 0, amnt });
}
int sz = ans.size();
cout << sz << endl;
reverse(ans.begin(), ans.end());
for (int i = 0; i < ans.size(); i++) {
cout << ans[i].first << " " << ans[i].second << endl;
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |