Submission #318677

#TimeUsernameProblemLanguageResultExecution timeMemory
318677ignaciocantaJetpack (COCI16_jetpack)C++14
80 / 80
30 ms20696 KiB
#include <bits/stdc++.h> using namespace std; using tint = long long; using ld = long double; #define forsn(i, s, n) for(int i = s; i < int(n); i++) #define forn(i, n) forsn(i, 0, n) using vi = vector<int>; #define pb push_back #define rsz resize #define all(x) begin(x), end(x) #define rall(x) x.rbegin(), x.rend() #define sz(x) (int)(x).size() using pi = pair<int,int>; #define f first #define s second #define mp make_pair #define DBG(x) cerr << #x << " = " << x << endl; const int MOD = 1e9+7; const int MX = 2e5+5; const tint INF = 2e18; const int inf = 2e9; const ld PI = acos(ld(-1)); void NACHO(string name = "protesta"){ ios_base::sync_with_stdio(0); cin.tie(0); // freopen((name+".in").c_str(), "r", stdin); //freopen((name+".out").c_str(), "w", stdout); } const int dx[4] = {1, -1, 0, 0}; const int dy[4] = {0, 0, 1, -1}; const int moveX[] = {-1, 1, 0}; const int moveY[] = {1, 1, 1}; bool valid(int x, int y, int n, int m){ return (0<=x && x<n && 0<=y && y<m); } const int NN = 15; const int MM = 1e5+5; bool visited[NN][MM]; pi vengo[NN][MM]; string tab[NN]; void dfs(int x, int y, int m){ //cout << x << " " << y << endl; visited[x][y] = 1; forn(k, 2){ int _x = x+moveX[k], _y = y+moveY[k]; if(valid(_x, _y, 10, m) && !visited[_x][_y] && tab[_x][_y] == '.'){ vengo[_x][_y] = mp(x, y); dfs(_x, _y, m); } } if(x == 9 || x == 0){ int _x = x+moveX[2], _y = y+moveY[2]; if(valid(_x, _y, 10, m) && !visited[_x][_y] && tab[_x][_y] == '.'){ vengo[_x][_y] = mp(x, y); dfs(_x, _y, m); } } } int main(){ NACHO(); int n; cin >> n; forn(i, 10) forn(j, n) vengo[i][j] = mp(-1, -1); forn(i, 10) cin >> tab[i]; dfs(9, 0, n); forn(j, 10){ if(visited[j][n-1]){ int X = j, Y = n-1; vector<pi> move; vector<pi> ret; while(!(X == -1 && Y == -1)){ move.pb(mp(X, Y)); auto u = vengo[X][Y]; X = u.f; Y = u.s; } reverse(all(move)); forn(i, sz(move)){ int j = i+1; bool e = 0; while(j < sz(move) && ((move[j].f == move[j-1].f && move[j].f == 0) || (move[j].f < move[j-1].f))){ e = 1; j++; } --j; //cout << i << " " << j << endl; if(e){ //cout << i << " " << j << endl; ret.pb(mp(i, j-i)); } i = j; } cout << sz(ret) << "\n"; for(auto u : ret){ cout << u.f << " " << u.s << "\n"; } return 0; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...