oj.uz

Submission #105937

# Submission time Handle Problem Language Result Execution time Memory
105937 2019-04-15T19:21:40 Z leonarda Jetpack (COCI16_jetpack) C++14
8 / 80
 86 ms 15824 KB 
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
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 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] != -1) {
			indeks = i;
			break;
		}
		
	int x = indeks, y = n - 1;
	int sek = 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;
		}
		
		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;
}

Compilation message

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

Subtask #1
8.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5504 KB Output is correct
2 Incorrect 7 ms 5504 KB Crashed with an obstacle
3 Incorrect 7 ms 5504 KB Crashed with an obstacle
4 Incorrect 7 ms 5632 KB Crashed with an obstacle
5 Incorrect 12 ms 5972 KB Crashed with an obstacle
6 Incorrect 15 ms 6272 KB Crashed with an obstacle
7 Incorrect 25 ms 7552 KB Crashed with an obstacle
8 Incorrect 53 ms 10588 KB Crashed with an obstacle
9 Incorrect 67 ms 13076 KB Crashed with an obstacle
10 Incorrect 86 ms 15824 KB Crashed with an obstacle