#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; // #define MAX_N 5000 // #define MAX_CALLS 70000 // #define fail(s, x...) do { \ // fprintf(stderr, s "\n", ## x); \ // exit(1); \ // } while(0) // /* Symbol obfuscation */ // #define N koala // #define realS kangaroo // #define realD possum // #define inv platypus // #define num_calls echidna // static int N; // static int realS[MAX_N]; // static int realD[MAX_N]; // static int inv[MAX_N]; // static int num_calls; // void answer(int S[], int D[]) { // int i; // int correct = 1; // for (i = 0; i < N; ++i) // if (S[i] != realS[i] || D[i] != realD[i]) { // correct = 0; // break; // } // if (correct) // printf("CORRECT\n"); // else // printf("INCORRECT\n"); // for (i = 0; i < N; ++i) { // if (i > 0) // printf(" "); // printf("%d", S[i]); // } // printf("\n"); // for (i = 0; i < N; ++i) { // if (i > 0) // printf(" "); // printf("%d", D[i]); // } // printf("\n"); // exit(0); // } // int tryCombination(int S[]) { // int i; // if (num_calls >= MAX_CALLS) { // printf("INCORRECT\nToo many calls to tryCombination().\n"); // exit(0); // } // ++num_calls; // for (i = 0; i < N; ++i) // if (S[inv[i]] != realS[inv[i]]) // return i; // return -1; // } // int init() { // int i, res; // cin >> N; // // res = fscanf(f, "%d", &N); // for (i = 0; i < N; ++i) { // cin >> realS[i]; // // res = fscanf(f, "%d", &realS[i]); // } // for (i = 0; i < N; ++i) { // cin >> realD[i]; // // res = fscanf(f, "%d", &realD[i]); // inv[realD[i]] = i; // } // num_calls = 0; // return N; // } 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; int now = tryCombination(q); if (now > i || now == -1) 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]) q[j] = s[j]; else cur.pb(j); } int l = 0, r = (int)cur.size() - 1, m, ans; 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]] = !s[cur[j]]; int now = tryCombination(q); if (now > i || now == -1) { ans = m; r = m - 1; } else l = m + 1; } d[cur[ans]] = i; used[cur[ans]] = 1; } answer(s, d); } // int main() { // int N; // N = init(); // exploreCave(N); // printf("INCORRECT\nYour solution did not call answer().\n"); // return 0; // }