перепиши этот код на питон #include <bits/stdc++.h> #include…
- User
перепиши этот код на питон #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #pragma GCC optimize("O3") #pragma GCC target("avx,avx2,popcnt,tune=native") #pragma GCC comment(linker, "/stack:200000000")
using namespace __gnu_pbds;
using namespace std; mt19937 rng(chrono::duration_castchrono::milliseconds(chrono::system_clock::now().time_since_epoch()).count());
constexpr int INF = 1e9 + 7, MD = 998244353, MAX = 200007, R = 1 << 19, MOD = 1040015701, MOD2 = 1e9 + 9, LG = 18, B = 40;
int rt, s; int sub[MAX], heavy[MAX], used[MAX], side_s[2]; vector g[MAX], query, side_v[2];
bool ask(vector & a, int v) { cout << "? " << (int)(a.size()) << ' ' << v; for (auto& u : a) cout << ' ' << u; cout << endl; bool f; cin >> f; return f; }
void dfs(int v, int p = 0) { sub[v] = 1, heavy[v] = 0; for (auto& u : g[v]) if (!used[u] && u != p) { dfs(u, v); sub[v] += sub[u], heavy[v] = max(heavy[v], sub[u]); } heavy[v] = max(heavy[v], s - sub[v]); if (!rt || heavy[v] < heavy[rt]) rt = v; }
signed main() { int n; cin >> n, s = n; for (int i = 1; i < n; ++i) { int u, v; cin >> u >> v; g[u].push_back(v), g[v].push_back(u); } int where = 1; while (true) { side_s[0] = side_s[1] = rt = 0; side_v[0].clear(), side_v[1].clear(), query.clear(); dfs(where); where = rt; dfs(where); for (auto& v : g[where]) if (!used[v]) query.push_back(v); if ((int)(query.size()) == 1) { bool f = ask(query, where); return !(cout << "! " << (f ? where : query[0]) << endl); } sort(query.begin(), query.end(), [&sub](int u, int v) { return sub[u] > sub[v]; }); for (auto& v : query) side_v[side_s[0] >= side_s[1]].push_back(v), side_s[side_s[0] >= side_s[1]] += sub[v]; bool f = !ask(side_v[0], where); s -= side_s[f]; for (auto& v : side_v[f]) used[v] = 1; } }
- Assistant
Переписать данный C++ код на Python представляет собой несколько сложную задачу, так как прямого аналога структур данных, использующихся в данном коде C++, в Python 'из коробки' нет. Я расскажу о ключевых компонентах и предложу python-версии для тех частей, которые могут быть адаптированы более непосредственно.
В исходном коде на C++ используется несколько продвинутых техник и библиотек:
__gnu_pbdsдля продвинутых структур данных (в Python можно использовать встроенные типы и библиотекуcollections).chronoиmt19937для генерирования случайных чисел (в Python можно использовать модульrandom).- Массивы и векторы для хранения данных (в Python это могут быть списки).
Я предлагаю реализацию на Python для части кода без использования специфических библиотек C++, сохраняя основную логику работы программы:
import random import time from collections import defaultdict INF = 10**9 + 7 MD = 998244353 MAX = 200007 R = 1 << 19 MOD = 1040015701 MOD2 = 10**9 + 9 LG = 18 B = 40 def ask(a, v): print(f"? {len(a)} {v}", *a) # В C++ реализации ожидается ответ от пользователя (или от другого процесса). # Здесь же мы просто вернем значение True/False принятое от пользователя или симуляции. f = input() == 'True' return f def dfs(v, g, used, p=0): sub = defaultdict(int) heavy = defaultdict(int) s = len(g) stack = [(v, p)] while stack: v, p = stack.pop() sub[v] = 1 heavy[v] = 0 for u in g[v]: if not used[u] and u != p: stack.append((u, v)) sub[v] += sub[u] heavy[v] = max(heavy[v], sub[u]) heavy[v] = max(heavy[v], s - sub[v]) rt = None for k in heavy: if rt is None or heavy[k] < heavy[rt]: rt = k return rt, sub def main(): n = int(input()) s = n g = defaultdict(list) for _ in range(1, n): u, v = map(int, input().split()) g[u].append(v) g[v].append(u) used = defaultdict(bool) where = 1 while True: side_s = [0, 0] side_v = [[], []] query = [] where, sub = dfs(where, g, used) for v in g[where]: if not used[v]: query.append(v) if len(query) == 1: f = ask(query, where) print(f"! {where if f else query[0]}") break # Sort and split the query based on subtree sizes query.sort(key=lambda u: sub[u], reverse=True) for v in query: idx = 0 if side_s[0] >= side_s[1] else 1 side_v[idx].append(v) side_s[idx] += sub[v] f = not ask(side_v[0], where) s -= side_s[int(f)] for v in side_v[int(f)]: used[v] = True if __name__ == "__main__": main()Этот код не включает некоторых продвинутых оптимизаций компилятора и алгоритмов из исходного кода C++, так как они применимы только в контексте С++. Вместо этого код фокусируется на алгоритмической стороне задачи.