Xoracle
Problem Statement
Subtask 1, limited degrees
We are guaranteed that each node has degree at most 3, and that there exist at least one node with degree 1, 2, and 3 respectively. Note that for any number , there exist no positive integer such that . As such, we can deduce the degree of node 1, by querying ? 1 i for each and noting what result isn't returned at any point. Once we know the degree of node 1, we can easily find the degree of any other node, since we already know , by using the following property of XOR: .
Subtask 2, limited degrees 2
We are guaranteed that each node has degree at most 4, and that at least 3 of the possible degrees are present in the tree. By realizing that if node 1 has degree 1, all query answers will be in the set .
Similar patterns can be seen for the other possible degrees, giving us the following combinations
By checking the cases with the giving answers, we can find the degree of node 1, and construct the solution as in subtask 1.
Subtask 3, ,
With , we have enough queries to recieve as much information as we want.
So, how can we construct the tree using the queries in time ?
We realize that at least one node must be a leaf. If we iterate over each node, and guess that this node is a leaf, we can calculate the total degree over all nodes of the tree. We now that this number needs to equal if the graph needs to be a valid tree. There is a second condition, however, which several contestants forgot. You need to check whether any node has degree 0, in the proposed solution. If so, the graph isn't connected, and furthermore it contains at least 1 cycle, and as such isn't a valid tree.
These 2 conditions are sufficient to construct the tree, and as such we have our solution to this subtask.
Subtask 4, ,
In this subtask we have fewer available queries than subtask 3. As such we have to observe, that if we at some point query and , and recieve the answer 0, node and must have the same degree. As such we say they are in the same "group". When we want to query two nodes, we can instead query any two nodes from the corresponding groups. By observing, that the number of groups is O(\sqrt{N}) we have reduced the problem to subtask 3.
Subtask 5, ,
By using the property of XOR used in subtask 1, we have reduced this subtask to subtask 3
Subtask 6,
By observing that the group of nodes representing the leaves (degree 1) is either the largest or second largest group, we can use our solution to subtask 5, but running in linear time.
Implementation
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int N, Q; cin >> N >> Q;
vector<int> cnt(N+1, 0);
cnt[0] = 1;
for (int i = 1; i < N; i++) {
cout << "? 1 " << i+1 << endl;
int x; cin >> x;
cnt[x]++;
}
int mx = 0, sec = 1;
if (cnt[0] < cnt[1]) swap(mx, sec);
for (int i = 2; i < N+1; i++) {
if (cnt[i] > cnt[mx]) {
sec = mx;
mx = i;
}
else if (cnt[i] > cnt[sec]) sec = i;
}
for (auto x : {mx, sec}) {
int sm = 0;
bool flag = 0;
for (int i = 0; i < N+1; i++) {
sm += cnt[i] * (i ^ x ^ 1);
flag |= cnt[i] > 0 && !(i ^ x ^ 1);
}
if (sm != 2 * N - 2 || flag) continue;
cout << '!';
for (int i = 0; i < N+1; i++)
while(cnt[i]--)
cout << ' ' << (i ^ x ^ 1);
cout << endl;
break;
}
}