#include "cave.h" #include <bits/stdc++.h> #include <bits/extc++.h> using namespace __gnu_pbds; using namespace std; // #pragma GCC optimize("Ofast") // #pragma GCC optimize ("unroll-loops") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #define ff first #define sc second #define pb push_back #define ll long long #define pll pair<ll, ll> #define pii pair<int, int> #define ull unsigned long long #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); mt19937_64 rngl(chrono::steady_clock::now().time_since_epoch().count()); // #define int long long // #define int unsigned long long // #define ordered_set(T) tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update> // #define ordered_multiset(T) tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update> // const ll mod = 1e9 + 7; // const ll mod = 998244353; const ll inf = 1e9; const ll biginf = 1e18; // const int maxN; void exploreCave(int n) { int s[n], d[n], q[n]{}; for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) q[j] = s[j]; for (int j = i; j < n; j++) q[j] = 0; if (tryCombination(q) >= i) s[i] = 0; else s[i] = 1; } bool used[n]{}; for (int i = 0; i < n; i++) { vector<int> cur; for (int j = 0; j < n; j++) { if (!used[j]) cur.pb(j); else q[j] = s[j]; } int l = 0, r = (int)cur.size() - 1, m, ans = -1; while (l <= r) { m = (l + r) / 2; for (int j = 0; j <= m; j++) q[cur[j]] = s[cur[j]]; for (int j = m + 1; j < cur.size(); j++) q[cur[j]] = 1 - s[cur[j]]; if (tryCombination(q) >= i) { ans = m; r = m - 1; } else l = m + 1; } d[i] = cur[ans]; used[cur[ans]] = 1; } answer(s, d); } // int32_t main() { // // #ifndef ONLINE_JUDGE // // freopen("input.txt", "r", stdin); // // freopen("output.txt", "w", stdout); // // #endif // ios_base::sync_with_stdio(false); // cin.tie(nullptr); cout.tie(nullptr); // int t = 1; // // cin >> t; // while (t--) { // solve(); // cout << '\n'; // } // return 0; // }