Fix an integer $$$x$$$, how could you find out the value of $$$y$$$?

Square both sides of the equation, for what values of $$$x$$$ is $$$x^2$$$ an integer?

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

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        for (int i = 0; i < n; i++) cout << i+1 << " ";
        cout << "\n";
    }
}

If we were to change the problem such that you could perform as many swaps as you wanted, the answer would remain the same.

Once our running sum encounters the maximum element of the array, the max of that prefix will always be the maximum element of the array.

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

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> vec(n); 
        for (auto &x: vec) cin >> x;

        cout << *max_element(vec.begin(), vec.end()) * n << "\n";
    }
}

Duplicate values don't matter, nor does the order of the elements.

Let's consider the inverse problem, where we have a array that is equal to [$0, 1, 2, \ldots, k-1$] and we can add $$$x$$$ to each value in the array. No matter which value of $$$x$$$ we choose, the values in $$$a$$$ are consecutive.

In order for the MEX to be greater than 0, 0 has to be contained in the array.

Since there are at most $$$3000$$$ elements in $$$a$$$, there are $$$3000$$$ possible values of $$$x$$$ that have a MEX greater than 0.

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

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> vec(n); 
        for (auto &x: vec) cin >> x;

        sort(vec.begin(), vec.end());
        // Remove duplicates
        vec.erase(unique(vec.begin(), vec.end()), vec.end());
        n = vec.size();
        int best = 0;
        int current = 0;
        for (int i = 0; i < n; i++) {
            if (i == 0 || vec[i] != vec[i-1]+1) {
                current = 0;
            }
            current++;
            best = max(best, current);
        }
        cout << best << "\n";
    }
}

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

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> vec(n); 
        for (auto &x: vec) cin >> x;

        sort(vec.begin(), vec.end());
        int best = 0;
        for (auto &x: vec) {
            int next = 0;
            for (int i = 0; i < vec.size(); i++) {
                if (vec[i]-x == next) next++;
            }
            best = max(best, next);
        }
        cout << best << "\n";
    }
}

Clearly, resetting all of the values is too slow, but we don't have to update all the elements at the same time.

If an element hasn't been modified after the last crash, it's value in the final array is the same as its value in the original array.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    int t;
    cin >> t;

    while (t--) {
        int n, m, k;
        cin >> n >> m >> k;

        vector<int> vec(n); for (auto &x: vec) cin >> x;
        vector<int> original_vec(n); for (int i = 0; i < n; i++) original_vec[i] = vec[i];
        vector<int> last_element_update(n, -1);
        int last_reset = -1;
        int reset_count = 0;
        for (int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            a--;

            if (last_element_update[a] < last_reset) vec[a] = original_vec[a];
            vec[a] += b;
            if (vec[a] > k) {
                last_reset = i;
                reset_count++;
                vec[a] = original_vec[a];
            }
            last_element_update[a] = i;
        }

        ll sum = 0;
        for (int i = 0; i < n; i++) {

            if (last_element_update[i] < last_reset) vec[i] = original_vec[i];
            cout << vec[i] << " ";
        }
        cout << "\n";


    }
}

Each robot's movements is independent of another robot's movements.

We only need to care about the spikes directly to the right and left of the robot, if they exist.

To figure out when a robot dies, we don't need to care about the position of the robot, only the distance to its left and right spikes.

We only care about the left-most a robot has been and the right-most a robot has been.

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

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n, m, k;
        cin >> n >> m >> k;

        vector<int> robots(n); for (auto &x: robots) cin >> x;

        vector<int> lava(m); for (auto &x: lava) cin >> x;

        vector<bool> dead(n); 
        map<int, vector<int>> death_locations;

        string instructions;
        cin >> instructions;

        sort(lava.begin(), lava.end());

        for (int i = 0; i < n; i++) {
            if (lava[0] < robots[i]) {
                int left_dist = robots[i] - (*(lower_bound(lava.begin(), lava.end(), robots[i]) - 1));
                death_locations[-left_dist].push_back(i);
            }
            if (lava[m-1] > robots[i]) {
                int right_dist = *lower_bound(lava.begin(), lava.end(), robots[i]) - robots[i];
                death_locations[right_dist].push_back(i);
            }
            
        }

        int current_pos = 0;
        int alive = n;

        for (auto &x: instructions) {
            if (x == 'L') current_pos--;
            else current_pos++;

            for (int i: death_locations[current_pos]) {
                
                if (dead[i]) continue;
                dead[i] = true;
                alive--;
            }
            death_locations[current_pos].clear();
            cout << alive << " ";
        }

        cout << "\n";
    }
}

A single cow will only face $$$n$$$ matches.

XOR is cumulative, meaning the order of the cows in a stack doesn't change its skill level.

Similarly, the order of the cows in the stack doesn't change the final position of the cow who was given the potion in the final line.

You can calculate range XOR queries in O(1) using prefix sum.

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

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n, q;
        cin >> n >> q;

        int num_cows = (1<<n);
        vector<int> cows(num_cows); for (auto &x: cows) cin >> x;

        vector<int> prefix(num_cows); prefix[0] = cows[0];
        for (int i = 1; i < num_cows; i++) {
            prefix[i] = cows[i] ^ prefix[i-1];
        }

        while (q--) {
            int cow_idx, skill_level;
            cin >> cow_idx >> skill_level;
            cow_idx--;

            int curr_position = 0;
            for (int i = 0; i < n; i++) {
                int size = (1<<i);
                int leader_idx = cow_idx / size;

                int leader_value = prefix[(size)*(leader_idx+1)-1] ^ (leader_idx == 0 ? 0 : prefix[(size)*(leader_idx)-1]);
                leader_value ^= cows[cow_idx];
                leader_value ^= skill_level;
                
                int enemy_value;
                if (leader_idx % 2 == 0) {
                    enemy_value = prefix[(size)*(leader_idx+2)-1] ^ prefix[(size)*(leader_idx+1)-1];
                }
                else {
                    enemy_value = prefix[(size)*(leader_idx)-1] ^ ((leader_idx-1) == 0 ? 0 : prefix[(size)*(leader_idx-1)-1]);
                }
                if (leader_value < enemy_value || (leader_value == enemy_value && leader_idx % 2 == 1)) {
                    curr_position += size;
                }
            }

            cout << curr_position << "\n";
        }
    } 
}

The only time adding an element changes the MEX of an array is if the added element is equal to the MEX of the array.

For a given element, the element is removed $$$n - 1$$$ times, and the element is added to another array $$$n - 1$$$ times.

We can treat removing an element from the array and adding it to another array as two separate interactions.

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
 
        vector<int> lengths(n);
        vector<vector<int>> arrays(n);
        map<int, int> count;
        for (int i = 0; i < n; i++) {
            int length;
            cin >> length;
            lengths[i] = length;
            arrays[i] = vector<int>(lengths[i]);
            for (auto &x: arrays[i]) {
                cin >> x;
                count[x]++;
            }
            sort(arrays[i].begin(), arrays[i].end());
        }
 
        int mex_sum = 0;
        vector<int> mexes(n);
        vector<int> second_mexes(n);
 
        // Calculate mex and second mex for each array
        for (int i = 0; i < n; i++) {
            int current_mex = 0;
            for (int j = 0; j < lengths[i]; j++) {
                if (arrays[i][j] > current_mex) break;
                if (arrays[i][j] == current_mex) current_mex++;
            }
            int second_mex = current_mex+1;
            for (int j = 0; j < lengths[i]; j++) {
                if (arrays[i][j] > second_mex) break;
                if (arrays[i][j] == second_mex) second_mex++;
            }
            mexes[i] = current_mex;
            second_mexes[i] = second_mex;
            mex_sum += current_mex;
        }
 
        ll total = 0;
        // Calculate removals
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < lengths[i]; j++) {
                ll org = total;
                bool is_alone = (j == 0 || arrays[i][j-1] != arrays[i][j]) && (j == lengths[i]-1 || arrays[i][j+1] != arrays[i][j]);
                if (is_alone && arrays[i][j] < mexes[i]) total += ((ll)(mex_sum-mexes[i]+arrays[i][j]))*(n-1);
                else total += (ll)(mex_sum) * (n-1);
            }
        }
        // Calculate additions
        for (int i = 0; i < n; i++) {
            total += (ll)(count[mexes[i]])*(second_mexes[i]-mexes[i]);
        }
 
        cout << total << "\n";
    }
    
}

I had originally proposed this problem with a subtask to solve for Cow 0 only, try that.

We can simulate each cow as if it started as position 0.

A cow only needs cheat at most $$$\log(max(a_i))$$$ times, since its skill level is (at least) double after each cheat.

Prefix sums, binary search, and helper methods are your friend.

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

#define ll long long

int main() {
    int t;
    cin >> t;

    int test_num = 0;
    while (t--) {
        int n, k;
        cin >> n >> k;
        test_num++;
        vector<ll> skill_levels(n); for (auto &x: skill_levels) cin >> x;
        
        vector<ll> prefix(n); prefix[0] = skill_levels[0];
        for (int i = 1; i < n; i++) prefix[i] = skill_levels[i] + prefix[i-1];

        auto sum_without_index = [&](int l, int r, int i) {
            if (r < l || r < 0 || l < 0) return 0ll;
            ll val = prefix[r] - (l == 0 ? 0 : prefix[l-1]);
            if (r < i) return val;
            if (l > i) {
                r++;
                l++;
                return prefix[r] - (l == 0 ? 0 : prefix[l-1]);
            }
            else {
                r++;
                return prefix[r] - (l == 0 ? 0 : prefix[l-1]) - skill_levels[i];
            }

        };

        auto bs_for_prefix = [&](ll target, int ignoring) {
            int lo = 0;
            int hi = n - 1;
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                if (mid == 0 || sum_without_index(0, mid-1, ignoring) < target) {
                    lo = mid + 1;
                }
                else {
                    hi = mid - 1;
                }
            }
            return hi;
        };

        vector<int> answer(n);
        for (int i = 0; i < n; i++) {        
            int last_starting_position = bs_for_prefix(skill_levels[i], i);

            vector<int> bad_positions;
            int pos = -1;
            
            while (true) {
                ll value = sum_without_index(0, pos, i) + skill_levels[i];

                ll pos_of_bad = bs_for_prefix(value * 2 + 1 - skill_levels[i], i);

                if (pos_of_bad >= n - 1) break;

                value = sum_without_index(0, pos_of_bad-1, i) + skill_levels[i];

                bool bad_position = sum_without_index(pos_of_bad, pos_of_bad, i) > value;

                if (bad_position) { 
                    bad_positions.push_back(pos_of_bad + 1);
                }
                pos = pos_of_bad;
            }
            
            if (k == 0) {
                if (bad_positions.size() == 0) answer[i] += last_starting_position + 1;
            }
            else if (bad_positions.size() > k) {
                answer[i] += n - bad_positions[bad_positions.size() - k];
            }
            else if (bad_positions.size() < k) {
                answer[i] += n;
            }
            else {
                answer[i] += min(n, (last_starting_position + 1) + (n - bad_positions[0]));
            }
        }

        for (auto &x: answer) cout << x << " ";
        cout << "\n";
        
    }
}