#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int NOT_VIS = 0;
const int CUR_VIS = 1;
const int VIS = 2;
map<pair<vector<int>, pair<int, int>>, pair<int, ll>> vis {};
/*ll arnaqueJpp(int pos, vector<int> vals, int carry, int dep) {
if (pos >= (int)vals.size() || pos < 0)
return 1e9;
if (dep > 15)
return 1e9;
//if (vis[{vals, {pos, carry}}].first)
//return vis[{vals, {pos, carry}}].second;
ll mnAns = 1e9;
//vis[{vals, {pos, carry}}] = {true, 1e9};
bool ok = true;
for (int i = 0; i < (int)vals.size(); i++)
if (vals[i] != i)
ok = false;
if (ok) {
//printf("food bruh %d %d\n", pos);
vis[{vals, {pos, carry}}] = {true, pos};
return pos;
}
mnAns = min(mnAns, 1 + recSolve(pos + 1, vals, carry, dep + 1));
mnAns = min(mnAns, 1 + recSolve(pos - 1, vals, carry, dep + 1));
int old = vals[pos];
vals[pos] = carry;
mnAns = min(mnAns, recSolve(pos, vals, old, dep + 1));
vals[pos] = old;
//vis[{vals, {pos, carry}}] = {true, mnAns};
return mnAns;
}*/
inline ll recSolve(int pos, vector<int> vals, int carry) {
if (pos >= (int)vals.size() || pos < 0)
return 1e9;
if (vis[{vals, {pos, carry}}].first == CUR_VIS)
return 1e9;
if (vis[{vals, {pos, carry}}].first == VIS)
return vis[{vals, {pos, carry}}].second;
ll mnAns = 1e9;
bool ok = true;
for (int i = 0; i < (int)vals.size(); i++)
if (vals[i] != i)
ok = false;
if (ok) {
//printf("food bruh %d %d\n", pos);
vis[{vals, {pos, carry}}] = {VIS, pos};
return pos;
}
vis[{vals, {pos, carry}}] = {CUR_VIS, 1e9};
mnAns = min(mnAns, 1 + recSolve(pos + 1, vals, carry));
mnAns = min(mnAns, 1 + recSolve(pos - 1, vals, carry));
int old = vals[pos];
vals[pos] = carry;
mnAns = min(mnAns, recSolve(pos, vals, old));
vals[pos] = old;
vis[{vals, {pos, carry}}] = {VIS, mnAns};
return mnAns;
}
ll minimum_walk(vector<int> p, int s) {
int n = (int)p.size();
return recSolve(0, p, -1) / 2;
/*vector<vector<int>> cycles {};
vector<bool> vis (n, false);
for (int i = 0; i < n; i++) {
if (vis[i])
continue;
//ans += abs(i - last);
int pos = i;
cycles.push_back({});
while (!vis[pos]) {
vis[pos] = true;
cycles.back().push_back(pos);
//ans += abs(p[pos] - pos);
pos = p[pos];
}
}
//ans += last;
vector<int> perm {};
for (int i = 0; i < (int)cycles.size(); i++)
perm.push_back(i);
do {
ll sub = 0;
int lst = 0;
for (int i = 0; i < (int)cycles.size(); i++) {
for (auto& x: cycles[i]) {
sub += abs(x - lst);
lst = x;
}
}
sub += lst;
ans = min(ans, sub);
} while (next_permutation(perm.begin(), perm.end()));
return ans;*/
}
Compilation message
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:76:9: warning: unused variable 'n' [-Wunused-variable]
76 | int n = (int)p.size();
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
468 KB |
3rd lines differ - on the 1st token, expected: '6', found: '5' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
468 KB |
3rd lines differ - on the 1st token, expected: '6', found: '5' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
468 KB |
3rd lines differ - on the 1st token, expected: '6', found: '5' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2080 ms |
223552 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
468 KB |
3rd lines differ - on the 1st token, expected: '6', found: '5' |
| 3 |
Halted |
0 ms |
0 KB |
- |
