| 19183 | 2025-11-28 14:35:06 | szil | Navigáció a toronyházban | cpp17 | Forditási hiba |
#include "navigacio.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int LE = 0;
const int BAL = 1;
const int JOBB = 2;
const int BFEL = 3;
const int JFEL = 4;
void navigate(vector<bool> layout) {
int asked = 0;
auto go_root = [&]() {
while (layout[LE]) layout = move(LE);
};
go_root();
vector<vector<pair<int, int>>> g(16);
vector<bool> exists(16);
vector<int> offset = {1, 2, 4, 8};
auto build = [&](auto &&self, int idx, int depth) -> int {
int v = offset[depth] + idx;
exists[v] = 1;
if (layout[JOBB]) {
g[v].emplace_back(v+1, 0);
}
if (layout[BAL]) {
g[v].emplace_back(v-1, 0);
}
if (depth != 3) {
bool bal = layout[BFEL];
bool jobb = layout[JFEL];
if (bal) {
layout = move(BFEL);
int nv = self(self, 2*idx, depth+1);
g[v].emplace_back(nv, 1);
g[nv].emplace_back(v, 1);
layout = move(LE);
}
if (jobb) {
layout = move(JFEL);
int nv = self(self, 2*idx+1, depth+1);
g[v].emplace_back(nv, 1);
g[nv].emplace_back(v, 1);
layout = move(LE);
}
}
return v;
};
build(build, 0, 0);
auto calc_dist = [&](int source) {
vector<int> dist(16, INF);
dist[source] = 0;
deque<int> q;
q.push_back(source);
while (!q.empty()) {
int u = q.front();
q.pop_front();
for (auto [v, w] : g[u]) {
if (dist[v] > dist[u] + 1) {
dist[v] = dist[u] + 1;
if (w) q.push_back(v);
else q.push_front(v);
}
}
}
return dist;
};
auto smart_query = [&](auto &&self, int idx, int depth, int need, int &res) -> void {
int v = offset[depth] + idx;
if (v == need) {
res = query();
asked++;
}
if (depth != 3) {
bool bal = layout[BFEL];
bool jobb = layout[JFEL];
if (bal) {
layout = move(BFEL);
self(self, 2*idx, depth+1, need, res);
layout = move(LE);
}
if (jobb) {
layout = move(JFEL);
self(self, 2*idx+1, depth+1, need, res);
layout = move(LE);
}
}
};
auto walk = [&](auto &&self, int idx, int depth, int need, int &found) -> void {
int v = offset[depth] + idx;
if (v == need) {
found = 1;
return;
}
if (depth != 3) {
bool bal = layout[BFEL];
bool jobb = layout[JFEL];
if (bal) {
layout = move(BFEL);
self(self, 2*idx, depth+1, need, found);
if (found) return;
layout = move(LE);
}
if (jobb) {
layout = move(JFEL);
self(self, 2*idx+1, depth+1, need, found);
if (found) return;
layout = move(LE);
}
}
};
bool extra = false;
int ml = -1, mr = -1;
for (int i = 8; i <= 15; i++) {
if (!exists[i]) continue;
for (int j = i; j <= 15; j++) {
if (!exists[j]) continue;
auto d1 = calc_dist(i);
auto d2 = calc_dist(j);
set<pair<int, int>> vals;
bool ok = true;
for (int k = 8; k <= 15; k++) {
if (!exists[k]) continue;
if (vals.count({d1[k], d2[k]})) ok = false;
vals.insert({dl[k], d2[k]});
}
if (ok) {
ml = i;
mr = j;
break;
}
}
}
int m;
bool fallback = false;
if (ml != -1) {
auto d1 = calc_dist(ml);
auto d2 = calc_dist(mr);
int x, y;
smart_query(smart_query, 0, 0, ml, x);
smart_query(smart_query, 0, 0, mr, y);
if ((x <= 20 || y <= 20)) {
fallback = true;
} else {
int cnt = 0, nxt = 0;
for (int i = 8; i <= 15; i++) {
if (!exists[i]) continue;
int m1 = x - d1[i];
int m2 = y - d2[i];
if (m1 == m2) {
nxt = i;
cnt++;
m = m1;
}
}
assert(cnt == 1);
int found = 0;
walk(walk, 0, 0, nxt, found);
}
} else {
fallback = true;
}
if (fallback) m = query();
while (true) {
if (m == 0) return;
bool bal = layout[BFEL];
bool jobb = layout[JFEL];
if (bal && !jobb) {
layout = move(BFEL);
m--;
} else if (!bal && jobb) {
layout = move(JFEL);
m--;
} else {
if (m == 1) {
layout = move(BFEL);
asked++;
if (query() != 0) move(JOBB);
return;
}
vector<bool> lb = move(BFEL);
vector<bool> lj = move(JOBB);
int c1 = 0;
c1 += lb[BFEL];
c1 += lb[JFEL];
int c2 = 0;
c2 += lj[BFEL];
c2 += lj[JFEL];
if (c1 <= 1 && c2 <= 1) {
int x = query();
asked++;
if (x == m-1) {
if (lj[BFEL]) layout = move(BFEL);
else layout = move(JFEL);
} else {
layout = move(BAL);
if (lb[BFEL]) layout = move(BFEL);
else layout = move(JFEL);
}
} else {
int D1 = (c2 == 2) ? BAL : JOBB;
int D2 = (c2 == 2) ? JFEL : BFEL;
int D3 = (c2 == 2) ? BFEL : JFEL;
if (c2 == 1) layout = move(BAL);
layout = move(D2);
int x = query();
asked++;
int y = m-2;
assert(x-y >= 0 && x-y <= 3);
int z = x-y;
if (z == 0) {
} else if (z == 1) {
layout = move(D1);
} else if (z == 2) {
layout = move(D1);
layout = move(D1);
} else {
layout = move(LE);
layout = move(D1);
layout = move(D3);
}
}
m -= 2;
}
}
}
open /var/local/lib/isolate/423/box/a.out: no such file or directory
main.cpp: In function 'void navigate(std::vector<bool>)':
main.cpp:138:30: error: 'dl' was not declared in this scope; did you mean 'd2'?
138 | vals.insert({dl[k], d2[k]});
| ^~
| d2
main.cpp:138:28: error: no matching function for call to 'std::set<std::pair<int, int> >::insert(<brace-enclosed initializer list>)'
138 | vals.insert({dl[k], d2[k]});
| ~~~~~~~~~~~^~~~~~~~~~~~~~~~
In file included from /usr/include/c++/12/set:61,
from /usr/include/x86_64-linux-gnu/c++/12/bits/stdc++.h:87,
from main.cpp:3:
/usr/include/c++/12/bits/stl_set.h:566:9: note: candidate: 'template<class _InputIterator> void std::set<_Key, _Compare, _Alloc>::insert(_InputIterator, _InputIterator) [with _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >]'
566 | insert(_InputIterator __first, _InputIterator __last)
| ^~~~~~
/usr/include/c++/12/bits/stl_set.h:566:9: note: template argument deduction/substitution failed:
main.cpp:138:28: note: candidate expects 2 arguments, 1 provided
138 | vals.insert({dl[k], d2[k]});
| ~~~~~~~~~~~^~~~~~~~~~~~~~~~
/usr/include/c++/12/bits/stl_set.h:509:7: note: candidate: 'std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Allocator>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(const value_type&) [with _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Allocator>::rebind<_Key>::other>::const_iterator = std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<in...