Submission #103625

#	Time	Username	Problem	Language	Result	Execution time	Memory
103625		leonarda	Jetpack (COCI16_jetpack)	C++14	8 / 80	102 ms	15864 KiB

jetpack

#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) 
		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;
		
		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;
	}
	
	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 (stderr)

jetpack.cpp: In function 'int main()':
jetpack.cpp:75:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if(exx - 1 == x and exy + 1 == y or (exx == x and x == 0))
      ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
jetpack.cpp:88:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < potezi.size(); ++i)
                 ~~^~~~~~~~~~~~~~~

• Subtask 1: 8 / 80