Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Ask only with two values. On inputs and , the hidden function becomes a monotone Boolean formula: is AND, is OR. Bowser is scary, not magical.
For a node of type where means and means , the value is the forcing value and is neutral. The node returns iff at least one of its top-level children returns .
For an interval , binary-search the first prefix set to that makes the answer , and the last suffix set to that makes the answer . Their order tells you whether the top operation is or .
After the top operation is known, set the whole interval to neutral . Binary-search from the left to find where the first child can be forced, and from the right to do the same for the last child. You only need some valid child boundary, not Bowser's exact original parentheses.
Initialize one query that forces the first child and one that forces the last child. Sweep from both ends, greedily keeping a variable if removing it kills the value . Once the processed prefix/suffix alone still returns , the last kept variable gives a split. Recurse. That's the whole damn castle map.
Only query values and . Subtract from the answer, so every query is over bits . Then
For a node, let mean it is a node, and mean it is a node. The cute symmetry is:
For , value is forcing and is neutral. For , value is forcing and is neutral. This is the main trick; everything else is just not tripping over the furniture.
We recursively recover an equivalent tree for an interval . We keep a vector of default values outside the interval so all already-separated siblings are neutralized.
If the current top operation is , then any boundary between two top-level children is a valid split, because and are associative:
So we do not need Bowser's exact parentheses. We only need an equivalent function. Huge difference. Saves us from ceremonial nonsense.
Define a prefix test: set to , set to , keep outside defaults fixed, and ask the function. This predicate is monotone in , so we can binary-search the first where the answer becomes .
Similarly, binary-search from the right: set a suffix to and the prefix before it to , and find the last suffix start that still gives .
Let these two positions be and .
If the top node is , a prefix can force the first child and a suffix can force the last child, so . If the top node is , to get answer every top-level child must be satisfied, so the prefix threshold is pushed to the right and the suffix threshold is pushed to the left, giving .
Thus:
Now suppose the current top operation is . Set the entire interval to the neutral value .
Use binary search twice from the left:
This lets us create a query that definitely forces the first child, without relying on later children. Do the symmetric thing from the right to create a query that forces the last child.
Now scan from both ends. For the left scan, try changing the current variable back to neutral. If the answer stops being , that variable is necessary, so keep it as . After each step, neutralize everything after the processed prefix. If the answer is still , the first top-level child is fully contained in the processed prefix, and the last necessary variable is exactly its right endpoint. Split there.
The right scan is the mirror image: it finds the left endpoint of the last top-level child, so we split right before it.
Scanning from both ends matters. If the first child is enormous but the last child is tiny, we find the right split fast, and vice versa.
For a segment of length , we spend queries on binary searches and scan queries, where is the distance to the nearer useful boundary. The recurrence is essentially
This sums to
queries over the whole reconstruction. With , this fits comfortably under queries. After reconstruction, each of Bowser's online inputs is answered by evaluating our recovered tree in time.
Reference used for sanity-checking the interactive strategy: Codeforces Round 1085 editorial.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
struct Node {
int l, r;
int left, right;
int op; // 1 = max, 0 = min
};
int n;
vector<Node> tree;
int readInt() {
int x;
if (!(cin >> x)) exit(0);
if (x == -1) exit(0);
return x;
}
int ask(const vector<int>& bit) {
cout << "?";
for (int i = 1; i <= n; i++) cout << ' ' << bit[i] + 1;
cout << endl;
int ans = readInt();
return ans - 1;
}
int bsFwd(int l, int r, int want, const vector<int>& defaults) {
int lo = l, hi = r;
while (lo < hi) {
int mid = (lo + hi) / 2;
vector<int> q = defaults;
for (int i = l; i <= mid; i++) q[i] = want;
for (int i = mid + 1; i <= r; i++) q[i] = want ^ 1;
if (ask(q) == want) hi = mid;
else lo = mid + 1;
}
return lo;
}
int bsRev(int l, int r, int want, const vector<int>& defaults) {
int lo = l, hi = r;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
vector<int> q = defaults;
for (int i = l; i < mid; i++) q[i] = want ^ 1;
for (int i = mid; i <= r; i++) q[i] = want;
if (ask(q) == want) lo = mid;
else hi = mid - 1;
}
return lo;
}
int recover(int l, int r, const vector<int>& defaults) {
if (l == r) {
tree.push_back({l, r, -1, -1, 1});
return (int)tree.size() - 1;
}
int s = bsFwd(l, r, 1, defaults);
int t = bsRev(l, r, 1, defaults);
int op = (s < t); // 1=max, 0=min
vector<int> neutral = defaults;
for (int i = l; i <= r; i++) neutral[i] = op ^ 1;
int mFwd = bsFwd(l, r, op, neutral);
int kFwd = bsFwd(mFwd + 1, r, op, neutral);
int mRev = bsRev(l, r, op, neutral);
int kRev = bsRev(l, mRev - 1, op, neutral);
vector<int> leftQ = neutral, rightQ = neutral;
for (int i = l; i < kFwd; i++) leftQ[i] = op;
for (int i = r; i > kRev; i--) rightQ[i] = op;
int leftTake = -1, rightTake = -1, cut = -1;
for (int step = 0; ; step++) {
int i = l + step;
leftQ[i] = op ^ 1;
if (ask(leftQ) != op) {
leftQ[i] = op;
leftTake = i;
}
vector<int> checkLeft = leftQ;
for (int j = i + 1; j <= r; j++) checkLeft[j] = op ^ 1;
if (ask(checkLeft) == op) {
cut = leftTake;
break;
}
int j = r - step;
rightQ[j] = op ^ 1;
if (ask(rightQ) != op) {
rightQ[j] = op;
rightTake = j;
}
vector<int> checkRight = rightQ;
for (int p = l; p < j; p++) checkRight[p] = op ^ 1;
if (ask(checkRight) == op) {
cut = rightTake - 1;
break;
}
}
int left = recover(l, cut, neutral);
int right = recover(cut + 1, r, neutral);
tree.push_back({l, r, left, right, op});
return (int)tree.size() - 1;
}
ll evalTree(int v, const vector<ll>& x) {
const Node& node = tree[v];
if (node.left == -1) return x[node.l];
ll a = evalTree(node.left, x);
ll b = evalTree(node.right, x);
return node.op ? max(a, b) : min(a, b);
}
int main() {
setIO();
int T = readInt();
while (T--) {
n = readInt();
tree.clear();
vector<int> defaults(n + 1, 0);
int root = recover(1, n, defaults);
cout << "!" << endl;
while (true) {
int first = readInt();
if (first == 0) break;
vector<ll> x(n + 1);
x[1] = first;
for (int i = 2; i <= n; i++) x[i] = readInt();
cout << evalTree(root, x) << endl;
}
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
struct Node {
int l, r;
int left, right;
int op; // 1 = max, 0 = min
};
int n;
vector<Node> tree;
int readInt() {
int x;
if (!(cin >> x)) exit(0);
if (x == -1) exit(0);
return x;
}
int ask(const vector<int>& bit) {
cout << "?";
for (int i = 1; i <= n; i++) cout << ' ' << bit[i] + 1;
cout << endl;
int ans = readInt();
return ans - 1;
}
int bsFwd(int l, int r, int want, const vector<int>& defaults) {
int lo = l, hi = r;
while (lo < hi) {
int mid = (lo + hi) / 2;
vector<int> q = defaults;
for (int i = l; i <= mid; i++) q[i] = want;
for (int i = mid + 1; i <= r; i++) q[i] = want ^ 1;
if (ask(q) == want) hi = mid;
else lo = mid + 1;
}
return lo;
}
int bsRev(int l, int r, int want, const vector<int>& defaults) {
int lo = l, hi = r;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
vector<int> q = defaults;
for (int i = l; i < mid; i++) q[i] = want ^ 1;
for (int i = mid; i <= r; i++) q[i] = want;
if (ask(q) == want) lo = mid;
else hi = mid - 1;
}
return lo;
}
int recover(int l, int r, const vector<int>& defaults) {
if (l == r) {
tree.push_back({l, r, -1, -1, 1});
return (int)tree.size() - 1;
}
int s = bsFwd(l, r, 1, defaults);
int t = bsRev(l, r, 1, defaults);
int op = (s < t); // 1=max, 0=min
vector<int> neutral = defaults;
for (int i = l; i <= r; i++) neutral[i] = op ^ 1;
int mFwd = bsFwd(l, r, op, neutral);
int kFwd = bsFwd(mFwd + 1, r, op, neutral);
int mRev = bsRev(l, r, op, neutral);
int kRev = bsRev(l, mRev - 1, op, neutral);
vector<int> leftQ = neutral, rightQ = neutral;
for (int i = l; i < kFwd; i++) leftQ[i] = op;
for (int i = r; i > kRev; i--) rightQ[i] = op;
int leftTake = -1, rightTake = -1, cut = -1;
for (int step = 0; ; step++) {
int i = l + step;
leftQ[i] = op ^ 1;
if (ask(leftQ) != op) {
leftQ[i] = op;
leftTake = i;
}
vector<int> checkLeft = leftQ;
for (int j = i + 1; j <= r; j++) checkLeft[j] = op ^ 1;
if (ask(checkLeft) == op) {
cut = leftTake;
break;
}
int j = r - step;
rightQ[j] = op ^ 1;
if (ask(rightQ) != op) {
rightQ[j] = op;
rightTake = j;
}
vector<int> checkRight = rightQ;
for (int p = l; p < j; p++) checkRight[p] = op ^ 1;
if (ask(checkRight) == op) {
cut = rightTake - 1;
break;
}
}
int left = recover(l, cut, neutral);
int right = recover(cut + 1, r, neutral);
tree.push_back({l, r, left, right, op});
return (int)tree.size() - 1;
}
ll evalTree(int v, const vector<ll>& x) {
const Node& node = tree[v];
if (node.left == -1) return x[node.l];
ll a = evalTree(node.left, x);
ll b = evalTree(node.right, x);
return node.op ? max(a, b) : min(a, b);
}
int main() {
setIO();
int T = readInt();
while (T--) {
n = readInt();
tree.clear();
vector<int> defaults(n + 1, 0);
int root = recover(1, n, defaults);
cout << "!" << endl;
while (true) {
int first = readInt();
if (first == 0) break;
vector<ll> x(n + 1);
x[1] = first;
for (int i = 2; i <= n; i++) x[i] = readInt();
cout << evalTree(root, x) << endl;
}
}
return 0;
}