Submission #103626

# Submission time Handle Problem Language Result Execution time Memory
103626 2019-04-01T10:44:56 Z leonarda Jetpack (COCI16_jetpack) C++14
8 / 80
96 ms 14968 KB
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
typedef pair<int, int> pi;
typedef long long int lint;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 5;

int n;
char a[13][maxn];
queue<int> qx, qy;
int memo[13][maxn];
pi put[13][maxn];
int mini = inf, indeks = -1;
vector<pi> potezi;

bool ok(int t1, int t2) {
	if(t1 < 0 or t2 < 0 or t1 >= 10 or t2 >= n) return 0;
	if(a[t1][t2] != '.' or memo[t1][t2] != -1) return 0;
	return 1;
}

int main ()
{
	ios::sync_with_stdio(0);
	
	cin >> n;
	for(int i = 0; i < 10; ++i)
		for(int j = 0; j < n; ++j)
			cin >> a[i][j];
	
	memset(memo, -1, sizeof memo);
	qx.push(9); qy.push(0);
	memo[9][0] = 0;
	
	while(!qx.empty()) {
		int x = qx.front();
		int y = qy.front();
		qx.pop(); qy.pop();
		
		if(ok(x + 1, y + 1)) {
			memo[x + 1][y + 1] = memo[x][y] + 1;
			qx.push(x + 1); qy.push(y + 1);
			put[x + 1][y + 1] = mp(x, y);
		}
		if(ok(x - 1, y + 1)) {
			memo[x - 1][y + 1] = memo[x][y] + 1;
			qx.push(x - 1); qy.push(y + 1);
			put[x - 1][y + 1] = mp(x, y);
		}
		if((x == 0 or x == 9) and ok(x, y + 1)) {
			memo[x][y + 1] = memo[x][y] + 1;
			qx.push(x); qy.push(y + 1);
			put[x][y + 1] = mp(x, y);
		}	
	}
/*	
	for(int i = 0; i < 10; ++i) {
		for(int j = 0; j < n; ++j)
			cout << memo[i][j] << " ";
		cout << endl;
	}
*/	
	for(int i = 0; i < 10; ++i) 
		if(memo[i][n - 1] < mini and memo[i][n - 1] != -1) 
			mini = memo[i][n - 1], indeks = i;
	
	int x = indeks, y = n - 1;
	int sek = 0;
//	int count = 0;
	
	while(memo[indeks][n - 1]--) {
		int exx = put[x][y].ff;
		int exy = put[x][y].ss;
		
		a[exx][exy] = '*';
		
		if(exx - 1 == x and exy + 1 == y or (exx == x and x == 0))
			++sek;
		else if(sek) {
			potezi.pb(mp(memo[indeks][n - 1], sek));
			sek = 0;
//			++count;
		}
		
		x = exx, y = exy;
	}
/*	
	for(int i = 0; i < 10; ++i) {
		for(int j = 0; j < n; ++j)
			cout << a[i][j];
		cout << endl;
	}
*/	
	cout << potezi.size() << endl;
	reverse(potezi.begin(), potezi.end());
	for(int i = 0; i < potezi.size(); ++i)
		cout << potezi[i].first << " " << potezi[i].second << endl;

return 0;
}
//written and directed by pcelicamaja

Compilation message

jetpack.cpp: In function 'int main()':
jetpack.cpp:81:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if(exx - 1 == x and exy + 1 == y or (exx == x and x == 0))
      ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
jetpack.cpp:100:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < potezi.size(); ++i)
                 ~~^~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 8 ms 5504 KB Output is correct
2 Incorrect 6 ms 5504 KB Crashed with an obstacle
3 Incorrect 6 ms 5504 KB Crashed with an obstacle
4 Incorrect 7 ms 5632 KB Crashed with an obstacle
5 Incorrect 13 ms 5888 KB Crashed with an obstacle
6 Incorrect 14 ms 6144 KB Crashed with an obstacle
7 Incorrect 23 ms 7424 KB Crashed with an obstacle
8 Incorrect 49 ms 10108 KB Crashed with an obstacle
9 Incorrect 72 ms 12404 KB Crashed with an obstacle
10 Incorrect 96 ms 14968 KB Crashed with an obstacle