A - Increment or Smash

Strategy: Direct simulation.

Every element that is not the global maximum will undergo a reset to zero followed by an increment, contributing exactly two steps to the total. However, identical values only incur this penalty once. The global maximum avoids the reset step altogether, naturally contributing just one step initially.

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

void process() {
    int len;
    cin >> len;
    vector<int> arr(len);
    for (int i = 0; i < len; ++i) cin >> arr[i];
    
    int max_val = *max_element(arr.begin(), arr.end());
    unordered_set<int> seen;
    int res = 1; // The maximum element requires 1 step
    
    for (int val : arr) {
        if (val != max_val && seen.find(val) == seen.end()) {
            res += 2;
            seen.insert(val);
        }
    }
    cout << res << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int test_cases;
    cin >> test_cases;
    while (test_cases--) process();
    return 0;
}

B - Catching the Krug

Strategy: Geometric casework.

The pursuer possesses the ability to move diagonal, meaning they can align their axis with the target's while advancing. The evader must flee towards the furthest boundary along the axis opposite to the pursuer's position. The result is simply the maximum of the distances the pursuer must travel along the x and y axes to intercept the evader at the boundaries.

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

void process() {
    int grid_size, pursuer[2], evader[2];
    cin >> grid_size >> pursuer[0] >> pursuer[1] >> evader[0] >> evader[1];
    
    int moves = 0;
    for (int axis = 0; axis < 2; ++axis) {
        if (pursuer[axis] < evader[axis]) {
            moves = max(moves, evader[axis]);
        } else if (pursuer[axis] > evader[axis]) {
            moves = max(moves, grid_size - evader[axis]);
        }
    }
    cout << moves << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int test_cases;
    cin >> test_cases;
    while (test_cases--) process();
    return 0;
}

C - Triple Removal

Strategy: Interval analysis via Segment Tree.

If a sequence contains adjacent identical bits (such as '00' or '11'), the entire block can be erased by consuming pairs, provided the total count of that bit is divisible by 3. Purely alternating sequences ('0101...') require one extra operation to create an adjacent pair. A segment tree can track whether an interval contains adjacent identical bits alongside their respective counts.

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

struct NodeData {
    int zero_cnt = 0, one_cnt = 0;
    int first_bit = -1, last_bit = -1;
    bool has_adj = false;
};

NodeData merge(NodeData left, NodeData right) {
    if (left.zero_cnt + left.one_cnt == 0) return right;
    if (right.zero_cnt + right.one_cnt == 0) return left;
    NodeData res;
    res.zero_cnt = left.zero_cnt + right.zero_cnt;
    res.one_cnt = left.one_cnt + right.one_cnt;
    res.first_bit = left.first_bit;
    res.last_bit = right.last_bit;
    res.has_adj = left.has_adj || right.has_adj || (left.last_bit == right.first_bit);
    return res;
}

vector<NodeData> tree;

void build(int idx, int l, int r, const vector<int>& arr) {
    if (l == r) {
        int v = arr[l - 1];
        tree[idx] = {1 - v, v, v, v, false};
        return;
    }
    int mid = (l + r) / 2;
    build(idx * 2, l, mid, arr);
    build(idx * 2 + 1, mid + 1, r, arr);
    tree[idx] = merge(tree[idx * 2], tree[idx * 2 + 1]);
}

NodeData query(int idx, int l, int r, int ql, int qr) {
    if (ql > r || qr < l) return {0, 0, -1, -1, false};
    if (ql <= l && r <= qr) return tree[idx];
    int mid = (l + r) / 2;
    return merge(query(idx * 2, l, mid, ql, qr), query(idx * 2 + 1, mid + 1, r, ql, qr));
}

void process() {
    int n, q;
    cin >> n >> q;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) cin >> arr[i];
    
    tree.resize(4 * n + 5);
    build(1, 1, n, arr);
    
    while (q--) {
        int ql, qr;
        cin >> ql >> qr;
        NodeData res = query(1, 1, n, ql, qr);
        if (res.zero_cnt % 3 != 0 || res.one_cnt % 3 != 0) {
            cout << "-1\n";
        } else {
            int steps = (qr - ql + 1) / 3;
            steps += (res.has_adj ? 0 : 1);
            cout << steps << "\n";
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int test_cases;
    cin >> test_cases;
    while (test_cases--) process();
    return 0;
}

D - Division Versus Addition

Strategy: Mathematical categorization.

Elements are grouped into Type A ($a_i = 2^k$), Type B ($a_i = 2^k + 1$), and Type C (others). Adding 1 to Type A incurs no extra penalty. Type B forces an additional operation when targeted, so the first player preemptively strikes Type B elements to halve the opponent's opportunities, contributing $\lfloor |B|/2 \rfloor$ to the penalty. Type C elements inevitably reach a state of $2^k-1$ after continuous additions, contributing exactly 1 extra penalty per element. The formula evaluates to $\sum \lfloer \log_2 a_i \rfloor + \lfloor |B|/2 \rfloor + |C|$.

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

struct SegNode {
    int total = 0;
    int odd_p2_remainder = 0; // tracks if an odd number of Type B elements exist
};

SegNode combine(SegNode a, SegNode b) {
    SegNode res;
    res.total = a.total + b.total + (a.odd_p2_remainder && b.odd_p2_remainder ? 1 : 0);
    res.odd_p2_remainder = (a.odd_p2_remainder + b.odd_p2_remainder) % 2;
    return res;
}

vector<SegNode> seg;

void build(int u, int l, int r, const vector<int>& data) {
    if (l == r) {
        int x = data[l - 1];
        int pw = 0;
        while ((1LL << (pw + 1)) <= x) pw++;
        bool is_p2 = (x == (x & -x));
        bool is_p2_plus_1 = ((x - 1) == ((x - 1) & -(x - 1))) && (x % 2 == 1);
        seg[u].total = pw + (!is_p2 && !is_p2_plus_1 ? 1 : 0);
        seg[u].odd_p2_remainder = is_p2_plus_1;
        return;
    }
    int mid = (l + r) / 2;
    build(u * 2, l, mid, data);
    build(u * 2 + 1, mid + 1, r, data);
    seg[u] = combine(seg[u * 2], seg[u * 2 + 1]);
}

SegNode query(int u, int l, int r, int ql, int qr) {
    if (ql > r || qr < l) return {0, 0};
    if (ql <= l && r <= qr) return seg[u];
    int mid = (l + r) / 2;
    return combine(query(u * 2, l, mid, ql, qr), query(u * 2 + 1, mid + 1, r, ql, qr));
}

void process() {
    int n, q;
    cin >> n >> q;
    vector<int> data(n);
    for (int i = 0; i < n; ++i) cin >> data[i];
    
    seg.resize(4 * n + 5);
    build(1, 1, n, data);
    
    while (q--) {
        int ql, qr;
        cin >> ql >> qr;
        cout << query(1, 1, n, ql, qr).total << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int test_cases;
    cin >> test_cases;
    while (test_cases--) process();
    return 0;
}

E - Monotone Subsequence

Strategy: Interactive graph traversal.

Query all indices. If the response contains a increasing subsequence of length $\ge n+1$, output it immediately. Otherwise, the returned indices partition the remaining elements into segments where each element is strictly smaller than the bounding returned index. Build a directed acyclic graph based on these topological constraints. The longest path in this DAG will yield a decreasing subsequence of length $\ge n+1$.

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

int n;

vector<int> ask(const vector<int>& indices) {
    cout << "? " << indices.size();
    for (int idx : indices) cout << " " << idx + 1;
    cout << endl;
    
    int k;
    cin >> k;
    vector<int> res(k);
    for (int i = 0; i < k; ++i) {
        cin >> res[i];
        res[i]--;
    }
    return res;
}

void output(const vector<int>& seq) {
    cout << "! ";
    for (int i = 0; i <= n; ++i) cout << seq[i] + 1 << " ";
    cout << endl;
}

void process() {
    cin >> n;
    vector<int> pool(n * n + 1);
    iota(pool.begin(), pool.end(), 0);
    
    vector<int> in_deg(n * n + 1, 0);
    vector<vector<int>> adj(n * n + 1);
    
    for (int iter = 0; iter < n; ++iter) {
        vector<int> ret = ask(pool);
        if (ret.size() >= n + 1) {
            output(ret);
            return;
        }
        
        vector<int> next_pool;
        int prev_bound = -1;
        for (int idx : pool) {
            auto it = upper_bound(ret.begin(), ret.end(), idx);
            int bound = (it == ret.begin() ? -1 : *(--it));
            
            if (idx == bound) continue;
            
            next_pool.push_back(idx);
            adj[bound].push_back(idx);
            in_deg[idx]++;
        }
        pool = move(next_pool);
    }
    
    vector<int> dist(n * n + 1, 1), parent(n * n + 1, -1);
    queue<int> q;
    for (int i = 0; i <= n * n; ++i) {
        if (in_deg[i] == 0) q.push(i);
    }
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            dist[v] = dist[u] + 1;
            parent[v] = u;
            if (dist[v] == n + 1) {
                vector<int> path;
                int cur = v;
                while (cur != -1) {
                    path.push_back(cur);
                    cur = parent[cur];
                }
                reverse(path.begin(), path.end());
                output(path);
                return;
            }
            if (--in_deg[v] == 0) q.push(v);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int test_cases;
    cin >> test_cases;
    while (test_cases--) process();
    return 0;
}