# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
558098 | nguyen31hoang08minh2003 | Jetpack (COCI16_jetpack) | C++14 | 16 ms | 14084 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
Saturday /\
May 7th, 2022 //\\
03:15 AM ///\\\
07/05/2022 //\\
UTC +07 ///\\\
////\\\\
///\\\
////\\\\
/////\\\\\
||
|| The tree
______||__________
*/
#include <bits/stdc++.h>
#define ALL(x) (x).begin(), (x).end()
#define SIZE(x) int((x).size())
template<class A, class B>
bool minimize(A &a, const B& b) {
return a <= b ? false : (a = b, true);
}
template<class A, class B>
bool maximize(A &a, const B& b) {
return a >= b ? false : (a = b, true);
}
template<class X, class Y>
std::ostream& operator << (std::ostream& outputStream, const std::pair<X, Y> &p) {
return outputStream << '{' << p.first << ", " << p.second >> '}';
}
template<class T>
std::ostream& operator << (std::ostream& outputStream, const std::vector<T>& values) {
outputStream << '{';
for (const T& value : values)
outputStream << value << ' ';
return outputStream << '}';
}
using namespace std;
const int ROWS = 10, MAX_N = 1e5 + 5;
signed main() {
int n;
string field[ROWS];
vector<pair<int, int> > result;
const function<bool(int, int)> DP = [&](const int x, const int y) -> bool {
static bool seen[ROWS][MAX_N]{}, dp[ROWS][MAX_N]{};
if (y >= n)
return true;
if (x < 0 || x >= ROWS || field[x][y] == 'X')
return false;
if (!seen[x][y]) {
seen[x][y] = true;
dp[x][y] = DP(max(0, x - 1), y + 1) || DP(min(x + 1, ROWS - 1), y + 1);
}
return dp[x][y];
};
const function<void(int, int, int)> trace = [&](const int x, const int y, const int z) {
if (y >= n) {
if (z)
result.emplace_back(y - z, z);
return;
}
if (DP(max(0, x - 1), y + 1))
trace(max(0, x - 1), y + 1, z + 1);
else {
if (z)
result.emplace_back(y - z, z);
trace(min(x + 1, ROWS - 1), y + 1, 0);
}
};
// freopen("input.INP", "r", stdin);
cin.tie(0) -> sync_with_stdio(0);
cout.tie(0);
cin >> n;
for (int x = 0; x < ROWS; ++x)
cin >> field[x];
trace(ROWS - 1, 0, 0);
cout << result.size() << '\n';
for (const auto& [t, x] : result)
cout << t << ' ' << x << '\n';
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |