Problem A

Each participant can compete in at most two consecutive rounds. This implies that the observer of the first round follows a repeating pattern: observe → compete → compete. Therefore, the k-th round involves the initial observer if and only if $ k \mod 3 = 1 $.

---

Problem B

Let $ S = \frac{n(n+1)}{2} $. If $ S $ is a perfect square, no valid permutation exists becuase the total sum would itself be a square, violating the condition.

Otherwise, construct the permutation greedily using a descending set of integers from 1 to $ n $. Maintain a running prefix sum and iteratively select the largest available number such that adding it does not result in a perfect square. This strategy leverages the fact that larger numbers help skip over dense regions of small perfect squares early on.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {
    ll n;
    cin >> n;
    ll total = n * (n + 1) / 2;
    ll root = sqrt(total);
    if (root * root == total) {
        cout << -1 << '\n';
        return;
    }

    set<ll, greater<ll>> nums;
    for (ll i = 1; i <= n; ++i) nums.insert(i);

    vector<ll> res;
    ll prefix = 0;
    while (!nums.empty()) {
        for (auto it = nums.begin(); it != nums.end(); ++it) {
            ll candidate = *it;
            ll new_sum = prefix + candidate;
            ll s = sqrt(new_sum);
            if (s * s != new_sum) {
                prefix = new_sum;
                res.push_back(candidate);
                nums.erase(it);
                break;
            }
        }
    }

    for (ll x : res) cout << x << ' ';
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
}

---

Problem C

Treat the destination node as the root of the tree. Perform a BFS starting from this root to collect nodes level by level. The required sequence is simply the reverse of this BFS traversal order—this ensures that cheese appears from deepest leaves upward, allowing the mouse to reach each layer without exceeding depth constraints.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {
    ll n, start, end;
    cin >> n >> start >> end;

    vector<vector<ll>> adj(n + 1);
    for (ll i = 0; i < n - 1; ++i) {
        ll u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<bool> visited(n + 1, false);
    vector<ll> order;
    queue<ll> q;
    q.push(end);

    while (!q.empty()) {
        ll u = q.front();
        q.pop();
        if (visited[u]) continue;
        visited[u] = true;
        order.push_back(u);
        for (ll v : adj[u]) {
            if (!visited[v]) q.push(v);
        }
    }

    for (int i = (int)order.size() - 1; i >= 0; --i) {
        cout << order[i] << ' ';
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
}

---

Problem D1

The sequence is extanded beyond index $ n $ with the rule: $$ a_{2m} = a_{2m+1} = a_1 \oplus a_2 \oplus \cdots \oplus a_m \quad \text{for } 2m > n. $$

Let $ X $ be the XOR of the first $ n $ elements. For queries with index $ l > n $, reduce $ l $ recursively:

• If $ n $ is even, compute $ a_{n+1} = X $ and treat $ n' = n + 1 $ (now odd).
• Then, for any $ l > 2n $, use the identity that pairs $ (a_{2m}, a_{2m+1}) $ cancel out when $ m > n $, so repeatedly halve $ l $ while toggling accumulated XOR based on parity.

Finally, once $ l \leq 2n $, directly compute the answer using precomputed values.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {
    ll n, l, r;
    cin >> n >> l >> r;
    vector<ll> a(n + 1);
    for (ll i = 1; i <= n; ++i) cin >> a[i];

    if (l <= n) {
        cout << a[l] << '\n';
        return;
    }

    vector<ll> pref(n + 1);
    for (ll i = 1; i <= n; ++i) pref[i] = pref[i - 1] ^ a[i];

    // Ensure n is odd
    if (n % 2 == 0) {
        n++;
        a.push_back(pref[n / 2]);
        pref.push_back(pref[n - 1] ^ a[n]);
    }

    // Extend up to 2n
    for (ll i = n + 1; i <= 2 * n; ++i) {
        a.push_back(pref[i / 2]);
        pref.push_back(pref[i - 1] ^ a[i]);
    }

    ll total_xor = pref[n];
    ll ans = 0;
    ll cur = l;

    while (cur > 2 * n) {
        ans ^= total_xor;
        cur /= 2;
        if ((cur - n) % 2 == 0) break;
    }

    ans ^= pref[cur / 2];
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
}