Submission #300019

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
300019	2020-09-16T06:52:39 Z	shrek12357	Jetpack (COCI16_jetpack)	C++14	80 / 80	125 ms	3576 KB

jetpack

#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 = 1e5+5;
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

jetpack.cpp: In function 'int main()':
jetpack.cpp:172:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  172 |  for (int i = 0; i < ans.size(); i++) {
      |                  ~~^~~~~~~~~~~~

Subtask #1

80.0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	4 ms	512 KB	Output is correct
6	Correct	7 ms	512 KB	Output is correct
7	Correct	21 ms	896 KB	Output is correct
8	Correct	51 ms	1784 KB	Output is correct
9	Correct	81 ms	2680 KB	Output is correct
10	Correct	125 ms	3576 KB	Output is correct