oj.uz

Submission #651093

# Submission time Handle Problem Language Result Execution time Memory
651093 2022-10-17T03:36:15 Z tuanvip870 Jetpack (COCI16_jetpack) C++14
80 / 80
 111 ms 10708 KB 
#include <bits/stdc++.h>
using namespace std;
// #define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef string str;
typedef pair <int, int> ii;
#define file "TEST"
#define st first
#define nd second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define vll vector<ll>
#define vi vector<int>
#define all(v) (v).begin(), (v).end()
#define FOR(i,x,y) for(ll i = x; i <= y; ++i)
#define FOS(i,x,y) for(ll i = x; i >= y; --i)
#define EACH(i,x) for (auto &(i) : (x))
#define el cout << '\n';
const ll MOD = 1e9 + 7;
#define dbg(...) cerr << "[" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "]  "
#define dbge(...) cerr << "[" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "]" << endl;

/*
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
*/

const int N = 2e5 + 5;;

int n, a[11][N];
vi res;

bool DFS(int i, int j) {
	if (a[i][j]) return 0;
	if (j == n) return 1;
	a[i][j] = 1;

	if (DFS(max(i - 1, 1), j + 1)) {
		res.pb(j - 1);
		return 1;
	}
	if (DFS(min(i + 1, 10), j + 1)) return 1;
	return 0;
}

void solve() {
	cin >> n;
	FOR(i, 1, 10) {
		FOR(j, 1, n) {
			char c; cin >> c;
			if (c == 'X') a[i][j] = 1;
		}
	}

	DFS(10, 1);

	cout << res.size() << '\n';
	FOS(i, res.size() - 1, 0) cout << res[i] << " 1" << endl;
}

signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    //freopen(file".INP","r",stdin);
    //freopen(file".OUT","w",stdout);

    ll t = 1;
    while(t--){
        solve();
    }
    
    return 0;
}

Subtask #1
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 6 ms 852 KB Output is correct
6 Correct 10 ms 1112 KB Output is correct
7 Correct 30 ms 2576 KB Output is correct
8 Correct 56 ms 5956 KB Output is correct
9 Correct 77 ms 8632 KB Output is correct
10 Correct 111 ms 10708 KB Output is correct