A single palindrome can have at most one character with an odd frequency (placed exactly in the middle). Since we need exactly two palindromes, our string $$$S$$$ can have a maximum of two characters with odd frequencies.

f you have exactly 2 characters with odd frequencies, they will serve as the centers of your two palindromes. But what if you have 1 or 0 odd frequencies? How do you ensure the second palindrome isn't empty?

You only need to guarantee that the second palindrome is valid and non-empty. Give the second palindrome the bare minimum characters it needs to exist, and dump all remaining even-frequency characters symmetrically into the first palindrome.

To solve this, we rely on character frequencies. Count the occurrences of each letter in the string $$$S$$$ and count how many of these letters have an odd frequency.

Here is the breakdown by the number of odd-frequency characters:

• More than 2 odds: It is mathematically impossible to form two palindromes. Output -1.

• Exactly 2 odds: This is the perfect scenario. Put one odd character in the center of the first palindrome, and the other odd character in the center of the second palindrome.

• Exactly 1 odd: Put the odd character in the center of the first palindrome. Because both palindromes must be non-empty, you need to "borrow" a pair of matching characters (frequency $$$\ge 2$$$) to form the second palindrome. If no such pair exists, it's impossible (output -1). If it does, use that pair to build the second palindrome.

• Exactly 0 odds: Since there are no odd characters to act as centers, you must find at least one pair of matching characters (frequency $$$\ge 2$$$). Split the pair: put one character in the center of the first palindrome, and the other in the center of the second palindrome. If no such pair exists, output -1.

Final Construction: Once you have satisfied the core requirements for the centers (and ensured the second palindrome isn't empty), you will only be left with pairs of characters (even frequencies). Take all remaining pairs, split them in half, and build out the left and right sides of your first palindrome.

/*
    Going back to the essence.

    Just another day on the moon,
    Cheese not included.
*/
#include <bits/stdc++.h>

#define endl '\n'
typedef long long ll;

using namespace std;

void solve(){
    string s;
    cin >> s;

    vector<int> freq(30, 0);

    for (char c : s) {
        ++freq[c - 'a'];
    }

    vector<char> odds;

    for (int i = 0 ; i < 26 ; ++i) {
        if (freq[i] & 1) {
            odds.push_back(i + 'a');
        }
    }

    if ((int) odds.size() > 2) {
        cout << "-1\n";
        return;
    }

    string p1_halt = "", p2_half = "";
    string p1_mid = "", p2_mid = "";

    if (odds.size() == 2) {
        p1_mid.push_back(odds[0]);
        p2_mid.push_back(odds[1]);
        freq[odds[0] - 'a']--;
        freq[odds[1] - 'a']--;
    } else if (odds.size() == 1) {
        p1_mid.push_back(odds[0]);
        freq[odds[0] - 'a']--;

        char tmp = 0;
        for (int i = 0 ; i < 26 ; ++i) {
            if (freq[i] >= 2) {
                tmp = 'a' + i;
                break;
            }
        }

        if (tmp == 0) {
            cout << "-1\n";
            return;
        }

        p2_half.push_back(tmp);
        freq[tmp - 'a'] -= 2;
    } else if (odds.size() == 0) {
        char tmp = 0;
        for (int i = 0 ; i < 26 ; ++i) {
            if (freq[i] >= 2) {
                tmp = 'a' + i;
                break;
            }
        }  

        if (tmp == 0) {
            cout << "-1\n";
            return;
        }

        p1_mid.push_back(tmp);
        p2_mid.push_back(tmp);
        freq[tmp - 'a'] -= 2;
    }

    for (int i = 0 ; i < 26 ; ++i) {
        char c = i + 'a';
        while (freq[i] > 0) {
            p1_halt.push_back(c);
            freq[i] -= 2;
        }
    }

    string p1_reverse = p1_halt;
    reverse(p1_reverse.begin(), p1_reverse.end());
    string p1 = p1_halt + p1_mid + p1_reverse;

    string p2_reverse = p2_half;
    reverse(p2_reverse.begin(), p2_reverse.end());
    string p2 = p2_half + p2_mid + p2_reverse;

    cout << p1 + p2 << '\n';
}


int main() {
    // Always chasing after that full moon glow
    // Warning: May cause howling at unusual times.
    #ifdef ONLINEJUDGE
       clock_t tStart = clock();
       freopen("input.txt","r",stdin), freopen("output.txt","w",stdout);
    #endif
    
    // Speed has never killed anyone ;)
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T = 1;
    // scanf("%d",&T);
    cin >> T;
    while(T--) solve();

    #ifdef ONLINEJUDGE
     fprintf(stderr, "\n>> Runtime: %.10fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
    #endif
    return 0;
}

What happens to the total number of '1's in string $$$a$$$ when you flip exactly two distinct bits? Try all three possible pairs you can flip: (0, 0), (1, 1), and (0, 1).

Flipping (0, 0) adds two '1's. Flipping (1, 1) removes two '1's. Flipping (0, 1) leaves the number of '1's unchanged. How does this affect the even/odd nature of the count of '1's in string $$$a$$$?

Even if the even/odd logic aligns, is there a maximum limit to how many '1's string $$$a$$$ can hold?

To solve this problem, we need to focus solely on the total count of '1's in both strings. Let $$$C_a$$$ be the number of '1's in string $$$a$$$, and $$$C_b$$$ be the number of '1's in string $$$b$$$.

Every time we perform the operation of flipping two bits in $$$a$$$, the value of $$$C_a$$$ changes by $$$+2$$$, $$$-2$$$, or $$$0$$$. Because the change is always an even number, the parity (whether the count is even or odd) of $$$C_a$$$ will never change, no matter how many operations you perform.

Therefore, for $$$a$$$ to eventually have exactly $$$C_b$$$ '1's, two conditions must be met:

• Matching Parity: $$$C_a$$$ and $$$C_b$$$ must be both even or both odd. If their parities differ, it is mathematically impossible to reach $$$C_b$$$.

• Capacity Limit: String $$$a$$$ cannot have more '1's than its total length. So, the target count $$$C_b$$$ must be less than or equal to the length of string $$$a$$$ ($$$C_b \le \vert{}a\vert{}$$$).

If both of these conditions are true, output YES. Otherwise, output NO.

/*
    Going back to the essence.
 
    Just another day on the moon,
    Cheese not included.
*/
#include <bits/stdc++.h>
 
#define endl '\n'
typedef long long ll;
 
using namespace std;
 
void solve(){
    string a, b;
 
    cin >> a >> b;
 
    int ca = count(a.begin(), a.end(), '1');
    int cb = count(b.begin(), b.end(), '1');
 
 
    if (((ca & 1) == (cb & 1)) and cb <= (int) a.length()) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
 }
 
 
int main() {
    // Always chasing after that full moon glow
    // Warning: May cause howling at unusual times.
    #ifdef ONLINEJUDGE
       clock_t tStart = clock();
       freopen("input.txt","r",stdin), freopen("output.txt","w",stdout);
    #endif
    
    // Speed has never killed anyone ;)
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T = 1;
    // scanf("%d",&T);
    cin >> T;
    while(T--) solve();
 
    #ifdef ONLINEJUDGE
     fprintf(stderr, "\n>> Runtime: %.10fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
    #endif
    return 0;
}

What happens to the elements of a single row when you cyclically shift all rows to the right? Does the set of numbers present in that row change?

Shifting all rows right preserves the exact set of elements in each row. Shifting all columns down just takes entire rows and moves them to new positions (row $$$i$$$ becomes row $$$i+1$$$). How does this affect the row MEXes?

Since the operations only rotate elements within a line or permute the lines entirely, they never actually alter the multiset of MEX values present in the grid. If you currently have a row with a MEX of $$$Y \neq X$$$, can you ever get rid of it?

To solve this problem, we must realize that the allowed operations are a complete red herring.

Let's look at the two operations:

• Cyclically shift all rows to the right: The elements in row $$$i$$$ stay in row $$$i$$$, they just change columns. The set of elements in each row is completely unchanged, so the MEX of each row stays exactly the same. (This operation just shifts the columns entirely, permuting the column MEXes).

• Cyclically shift all columns down: The elements in column $$$j$$$ stay in column $$$j$$$, they just change rows. The set of elements in each column is completely unchanged, so the MEX of each column stays exactly the same. (This operation just shifts the rows entirely, permuting the row MEXes).

Neither operation can change the actual values of the MEXes present in the grid; they can only shuffle which row or column has which MEX. Therefore, for it to be possible for every row to have a MEX of $$$X$$$ and every column to have a MEX of $$$X$$$, they must all already equal $$$X$$$ from the very beginning.

Simply iterate through the original grid and calculate the MEX for each of the $$$N$$$ rows and each of the $$$N$$$ columns. If all $$$2N$$$ of these MEX values are exactly equal to $$$X$$$, output YES. If even a single row or column has a MEX different from $$$X$$$, output NO.

/*
    Going back to the essence.

    Just another day on the moon,
    Cheese not included.
*/
#include <bits/stdc++.h>

#define endl '\n'
typedef long long ll;

using namespace std;

int n, x;

int get_mex(const vector<int>& v) {
    vector<bool> vis(n + 1, false);
    for (int val : v) {
        if (val <= n) {
            vis[val] = true;
        }
    }

    int mex = 0;
    while (vis[mex]) ++mex;
    return mex;
}

void solve(){
    cin >> n >> x;

    vector<vector<int>> a(n, vector<int>(n));
    for (int i = 0 ; i < n ; ++i) {
        for (int j = 0 ; j < n ; ++j) {
            cin >> a[i][j];
        }
    }

    for (int i = 0 ; i < n ; ++i) {
        if (get_mex(a[i]) != x) {
            cout << "NO\n";
            return;
        }
    }

    for (int j = 0 ; j < n ; ++j) {
        vector<int> col(n);
        for (int i = 0 ; i < n ; ++i) {
            col[i] = a[i][j];
        }

        if (get_mex(col) != x) {
            cout << "NO\n";
            return;
        }
    }

    cout << "YES\n";
}


int main() {
    // Always chasing after that full moon glow
    // Warning: May cause howling at unusual times.
    #ifdef ONLINEJUDGE
       clock_t tStart = clock();
       freopen("input.txt","r",stdin), freopen("output.txt","w",stdout);
    #endif
    
    // Speed has never killed anyone ;)
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T = 1;
    // scanf("%d",&T);
    cin >> T;
    while(T--) solve();

    #ifdef ONLINEJUDGE
     fprintf(stderr, "\n>> Runtime: %.10fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
    #endif
    return 0;
}

The operation $$$a_i = a_i - a_j$$$ (where $$$a_j \le a_i$$$) is the exact subtraction step used in a famous algorithm. If you perform this repeatedly on two adjacent positive numbers, they will eventually reduce to a certain number $$$g$$$ and $$$0$$$.

If you can reduce an adjacent pair to their GCD and a $$$0$$$, you can then use that new GCD to reduce the next adjacent number. For any contiguous block of numbers, you can collapse the entire block down to a single non-zero number: the GCD of the whole block.

Can a $$$0$$$ help reduce its neighbors? Subtracting $$$0$$$ from $$$a_i$$$ leaves $$$a_i$$$ unchanged. Can a $$$0$$$ be reduced? No, because $$$a_j \le 0$$$ means $$$a_j$$$ must also be $$$0$$$. Therefore, any existing $$$0$$$ in the array acts as an impenetrable wall that splits the array into completely independent blocks.

The core realization is that the given operation simulates the Euclidean algorithm. By repeatedly subtracting a smaller adjacent element from a larger one, any contiguous block of positive integers can be optimally reduced so that all elements become $$$0$$$ except for exactly one element. The value of this final remaining element will be the GCD of all the initial numbers in that block.

However, the operations cannot jump across existing $$$0$$$s. Because subtracting $$$0$$$ from a number does nothing, the initial $0$s in the cart act as boundaries. They divide the array into isolated, independent subsegments of positive numbers.

1. Traverse the array from left to right.

2. Maintain a running GCD for the current block of positive numbers.

3. If you encounter a $$$0$$$, the current block ends. Add the block's running GCD to your total minimum sum, and reset the running GCD back to $$$0$$$.

4. If you encounter a positive number, update your running GCD using g = gcd(g, a[i]).

5. After finishing the loop, don't forget to add the running GCD of the final block to your total sum.

The final total sum of these block GCDs is the absolute minimum sum you can achieve.

/*
    Going back to the essence.

    Just another day on the moon,
    Cheese not included.
*/
#include <bits/stdc++.h>

#define endl '\n'
typedef long long ll;

using namespace std;

long long gcd(long long a, long long b) {
    if (!b)
        return a;
    return gcd(b, a%b);
}

void solve(){
    int n;
    cin >> n;
    vector<long long> a(n);

    for (auto &x : a) {
        cin >> x;
    }

    long long ans = 0, g = 0;

    for (int i = 0 ; i < n ; ++i) {
        if (a[i] == 0) {
            ans += g;
            g = 0;
        } else {
            if (g == 0) {
                g = a[i];
            } else {
                g = gcd(g, a[i]);
            }
        }
    }

    ans += g;

    cout << ans << '\n';
}


int main() {
    // Always chasing after that full moon glow
    // Warning: May cause howling at unusual times.
    #ifdef ONLINEJUDGE
       clock_t tStart = clock();
       freopen("input.txt","r",stdin), freopen("output.txt","w",stdout);
    #endif
    
    // Speed has never killed anyone ;)
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T = 1;
    // scanf("%d",&T);
    cin >> T;
    while(T--) solve();

    #ifdef ONLINEJUDGE
     fprintf(stderr, "\n>> Runtime: %.10fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
    #endif
    return 0;
}

Think about how the MEX changes as the prefix grows. When you add a new number to the prefix, you are only adding to the set of available numbers. Therefore, the MEX can either stay the same or increase—it can never decrease.

As you read the array from left to right, use a simple frequency array or a boolean array (let's call it vis) to keep track of the numbers you have encountered so far.

If you keep a running variable for your current mex starting at 0, you don't need to recalculate it from 0 for every prefix. When vis[mex] becomes true, just keep incrementing mex until you hit a number you haven't seen yet.

The key to solving this problem efficiently is realizing that the MEX is monotonically non-decreasing. Because we are only ever adding elements to our prefix, the smallest missing positive integer can only shift upwards.

We can solve this in $$$O(n)$$$ time using a boolean array vis of size $$$n+1$$$ (initialized to false) and a single variable mex initialized to 0.

1. Iterate through the array elements $$$a_i$$$ from left to right.

2. For each element, if $$$a_i \le n$$$, mark it as seen by setting vis[a_i] = true. (We can ignore numbers greater than $$$n$$$ because the MEX of an array of length $$$n$$$ can never exceed $$$n$$$).

3. Check if your current mex has been found. Use a while loop: while (vis[mex] is true) { ++mex; }.

4. The loop will stop at the smallest number that hasn't been marked yet. This is your MEX for the current prefix. Print it.

Even though there is a while loop nested inside the for loop, the mex variable is never reset to 0. It only ever increments. Across all n iterations of the outer loop, the inner while loop will only advance a total of at most n times. This guarantees a highly efficient O(n) time complexity.

/*
    Going back to the essence.

    Just another day on the moon,
    Cheese not included.
*/
#include <bits/stdc++.h>

#define endl '\n'
typedef long long ll;

using namespace std;

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);

    for (int i = 0 ; i < n ; ++i) {
        cin >> a[i];
    }

    vector<bool> vis(n + 1, false);
    int mex = 0;

    for (int i = 0 ; i < n ; ++i) {
        if (a[i] <= n) {
            vis[a[i]] = true;
        }

        while (mex <= n and vis[mex]) ++mex;

        cout << mex << (i == n - 1 ? "" : " ");
    }
    cout << '\n';
}


int main() {
    // Always chasing after that full moon glow
    // Warning: May cause howling at unusual times.
    #ifdef ONLINEJUDGE
       clock_t tStart = clock();
       freopen("input.txt","r",stdin), freopen("output.txt","w",stdout);
    #endif
    
    // Speed has never killed anyone ;)
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T = 1;
    // scanf("%d",&T);
    cin >> T;
    while(T--) solve();

    #ifdef ONLINEJUDGE
     fprintf(stderr, "\n>> Runtime: %.10fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
    #endif
    return 0;
}

To form ->, the dash (-) must appear before the >. To form <-, the dash (-) must appear after the <.

A dash at the very beginning of the string is great for -> but completely useless for <-. Conversely, a dash at the very end is perfect for <- but useless for ->. This suggests a greedy strategy: allocate the leftmost dashes to > and the rightmost dashes to <.

Keep track of all available dashes. Do one pass from left to right to greedily pair > with the earliest available dashes. Then, do a second pass from right to left to pair < with the latest available leftover dashes.

To maximize the number of arrows, we must manage our pool of dashes ($$$-$$$) efficiently. Since -> requires the dash to be on the left, and <- requires the dash to be on the right, we can safely prioritize giving the leftmost dashes to > and saving the rightmost dashes for <.

We can implement this using a double-ended queue (deque) to store the indices of the dashes.

1. Pass 1 (Left to Right): Iterate through the string.

• If you see a $$$-$$$, push its index to the back of the deque.
• If you see a >, check if your deque has any dashes. If it does, pair the > with the front (leftmost) dash in the deque, pop that dash, and increment your answer.

1. Pass 2 (Right to Left): Iterate through the string backwards.

• If you see a <, check if your deque has any dashes left. Look at the back (rightmost) dash. If its index is greater than your current index, it means the dash comes after the <, which forms a valid <-. Pair them up, pop the back of the deque, and increment your answer.

By greedily consuming the leftmost dashes for -> and the rightmost dashes for <-, you guarantee the maximum possible number of constructed arrows.

/*
    Going back to the essence.

    Just another day on the moon,
    Cheese not included.
*/
#include <bits/stdc++.h>

#define endl '\n'
typedef long long ll;

using namespace std;

void solve(){
    string s;
    cin >> s;

    const int n = (int) s.size();

    deque<int> dashes;
    int ans = 0;

    for (int i = 0; i < n; i++) {
        if (s[i] == '-') {
            dashes.push_back(i);
        } else if (s[i] == '>') {
            if (!dashes.empty()) {
                dashes.pop_front();
                ans++;
            }
        }
    }
    
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == '<') {
            if (!dashes.empty() && dashes.back() > i) {
                dashes.pop_back();
                ans++;
            }
        }
    }

    cout << ans << '\n';


}


int main() {
    // Always chasing after that full moon glow
    // Warning: May cause howling at unusual times.
    #ifdef ONLINEJUDGE
       clock_t tStart = clock();
       freopen("input.txt","r",stdin), freopen("output.txt","w",stdout);
    #endif
    
    // Speed has never killed anyone ;)
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T = 1;
    // scanf("%d",&T);
    cin >> T;
    while(T--) solve();

    #ifdef ONLINEJUDGE
     fprintf(stderr, "\n>> Runtime: %.10fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
    #endif
    return 0;
}

Are the numbers already equal? That's 0 operations. Does applying a single Sync operation make them equal? That's 1 operation.

Try an Upgrade followed by a Sync. If $$$\gcd(a, c+1) = \gcd(b, c+1)$$$, you can make them equal in exactly 2 operations.

Is there a sequence of operations that guarantees $$$a=b$$$ no matter what the initial numbers are? Think about the mathematical property of consecutive integers: $$$\gcd(X, X+1) = 1$$$.

The key realization to solve this problem is that the maximum number of operations you will ever need is 3.

Let's see why: If you perform a Sync operation, $$$a$$$ and $$$b$$$ become divisors of $$$c$$$.

If you then perform an Upgrade, the new token power becomes $$$c+1$$$.

Because consecutive integers are always coprime (they share no common factors other than 1), $$$\gcd(c, c+1) = 1$$$. This means the new $$$c+1$$$ is also completely coprime to the current values of $$$a$$$ and $$$b$$$ (which are divisors of $$$c$$$).

If you perform a final Sync, both $$$a$$$ and $$$b$$$ will become exactly $$$1$$$.This sequence (Sync $$$\rightarrow$$$ Upgrade $$$\rightarrow$$$ Sync) takes exactly 3 operations and guarantees $$$a = b = 1$$$.

Since the maximum answer is always 3, we just need to check if we can do it in fewer operations: - If $$$a = b$$$, output 0.

• Else if $$$\gcd(a, c) = \gcd(b, c)$$$, a single Sync works. Output 1.

• Else if $$$\gcd(a, c+1) = \gcd(b, c+1)$$$, an Upgrade then a Sync works. Output 2.

• Otherwise, the guaranteed 3-operation sequence is optimal. Output 3.

/*
    Going back to the essence.

    Just another day on the moon,
    Cheese not included.
*/
#include <bits/stdc++.h>

#define endl '\n'
typedef long long ll;

using namespace std;

long long gcd(long long a, long long b) {
    if (!b)
        return a;
    return gcd(b, a%b);
}

void solve(){
    long long a, b, c;
    cin >> a >> b >> c;

    if (a == b) {
        cout << 0 << '\n';
    } else if (gcd(a, c) == gcd(b, c)) {
        cout << 1 << '\n';
    } else if (gcd(a, c + 1) == gcd(b, c + 1)) {
        cout << 2 << '\n';
    } else {
        cout << 3 << '\n';
    }
}


int main() {
    // Always chasing after that full moon glow
    // Warning: May cause howling at unusual times.
    #ifdef ONLINEJUDGE
       clock_t tStart = clock();
       freopen("input.txt","r",stdin), freopen("output.txt","w",stdout);
    #endif
    
    // Speed has never killed anyone ;)
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T = 1;
    // scanf("%d",&T);
    cin >> T;
    while(T--) solve();

    #ifdef ONLINEJUDGE
     fprintf(stderr, "\n>> Runtime: %.10fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
    #endif
    return 0;
}

Every time you make a straight cut completely through the center of a circle, how does the number of pieces change?

Because the cuts go all the way across and pass through the center, each distinct cut creates exactly two new slices. Therefore, making N distinct cuts will always divide the pizza into exactly 2N slices.

Shaaker demands a strictly prime number of slices. Knowing that the total number of slices is always even (2N), what is the only even prime number in mathematics?

Every straight cut passing through the center of the pizza creates exactly 2 pieces. Therefore, if Tardi makes N distinct cuts, the pizza will always be divided into exactly 2N slices.

The problem requires the final number of slices to be a prime number.

• The only even prime number that exists is 2.
• To get exactly 2 slices, Tardi must make exactly 1 cut (2 * 1 = 2).

If N = 0, there is 1 slice, and 1 is not a prime number. If N > 1, the number of slices will be an even number greater than 2, meaning it is composite and cannot be prime.

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    if (n == 1) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}

Moon can only clear the line if his jump height $$$h$$$ is strictly greater than the height of every single enemy in the line.

If there is even one enemy whose height $$$a_i$$$ is greater than or equal to $$$h$$$, Moon will fail.

If Moon can jump over the tallest enemy in the line, he can jump over all of them. So, you just need to check if $$$h$$$ is strictly greater than the maximum $$$a_i$$$.

To solve this problem, we need to check if Moon's jump height $$$h$$$ is strictly greater than every element in the array $$$a$$$.The easiest way to do this is to iterate through the given heights $$$a_1, a_2, \dots, a_n$$$ as they are provided. For each height, check if $$$h \le a_i$$$.

• If you find any enemy where $$$h \le a_i$$$, it means Moon's jump height is not enough to clear that enemy. Set a flag to false.

• If the loop finishes and the flag is still true, it means $$$h$$$ was strictly greater than every single enemy's height.

/*
    Going back to the essence.

    Just another day on the moon,
    Cheese not included.
*/
#include <bits/stdc++.h>

#define endl '\n'
typedef long long ll;

using namespace std;

void solve(){
    int n, h;

    cin >> n >> h;
    bool flag = true;

    for (int x, i = 0 ; i < n ; ++i) {
        cin >> x;
        if (h <= x) 
            flag = false;
    }

    cout << (flag ? "YES" : "NO") << '\n';
}


int main() {
    // Always chasing after that full moon glow
    // Warning: May cause howling at unusual times.
    #ifdef ONLINEJUDGE
       clock_t tStart = clock();
       freopen("input.txt","r",stdin), freopen("output.txt","w",stdout);
    #endif
    
    // Speed has never killed anyone ;)
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T = 1;
    // scanf("%d",&T);
    cin >> T;
    while(T--) solve();

    #ifdef ONLINEJUDGE
     fprintf(stderr, "\n>> Runtime: %.10fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
    #endif
    return 0;
}

You just need to scan the string from left to right one character at a time. The moment you see the first 'C', you have found your answer.

To solve this problem, we need to find the first occurrence of the character 'C' in the given string and output its position.

We can achieve this by iterating through the string from left to right. As soon as we encounter a 'C', we immediately print its position and stop the program.

/*
    Going back to the essence.

    Just another day on the moon,
    Cheese not included.
*/
#include <bits/stdc++.h>

#define endl '\n'
typedef long long ll;

using namespace std;

void solve(){
    string s;
    cin >> s;

    for (int i = 0 ; i < (int) s.size() ; ++i) {
        if (s[i] == 'C') {
            cout << i + 1 << '\n';
            return;
        }
    }
    cout << "-1\n";
}


int main() {
    // Always chasing after that full moon glow
    // Warning: May cause howling at unusual times.
    #ifdef ONLINEJUDGE
       clock_t tStart = clock();
       freopen("input.txt","r",stdin), freopen("output.txt","w",stdout);
    #endif
    
    // Speed has never killed anyone ;)
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T = 1;
    // scanf("%d",&T);
    cin >> T;
    while(T--) solve();

    #ifdef ONLINEJUDGE
     fprintf(stderr, "\n>> Runtime: %.10fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
    #endif
    return 0;
}

A fundamental property of XOR is that the XOR sum of three identical values is the value itself ($$$X \oplus X \oplus X = X$$$). If we can embed $$$X$$$ into the lower bits of all three terms, we are halfway there.

To safely manipulate higher bits without ruining the $$$X$$$ in the lower bits, use a massive power of 2 that is strictly greater than $$$X$$$. Let $$$M = 2^{60}$$$. Adding multiples of $$$M$$$ will not cause any carry operations into the bits of $$$X$$$.

You need the extra high bits you introduce to cancel each other out via XOR. Can you pick a starting point $$$a$$$ and a step size $$$b$$$ that produce the binary patterns 01, 10, and 11 in those high bit positions?

To solve this mathematically, we want to completely isolate the bits of $$$X$$$ from the bits we use to form the arithmetic progression. We can do this by operating in bit ranges far larger than $$$X$$$.

Let $$$M = 2^{60}$$$.We set our starting value to $$$a = M + X$$$, and our step size to $$$b = M$$$.Let's evaluate the three terms of our arithmetic progression:

• First term: $$$a = M + X$$$

• Second term: $$$a + b = 2M + X$$$

• Third term: $$$a + 2b = 3M + X$$$

Because $$$M$$$ is a power of 2, adding $$$M$$$ and $$$2M$$$ is equivalent to setting specific high bits. The term $$$3M$$$ is exactly $$$2M + M$$$, meaning both the $$$M$$$ bit and the $$$2M$$$ bit are set to 1.

Now, let's look at the bitwise XOR sum of these three terms:

Since $$$X$$$ is much smaller than $$$M$$$, there is no overlapping between the bits of $$$X$$$ and the bits of $$$M$$$, $$$2M$$$, or $$$3M$$$. Therefore, we can evaluate the high bits and low bits independently:

The high bits perfectly cancel out: $$$M \oplus 2M \oplus (M + 2M) = 0$$$.The low bits evaluate to our target: $$$X \oplus X \oplus X = X$$$.

you can think about why M = 2^{60}, or any power that is bigger than $$$X$$$

/*
    Going back to the essence.

    Just another day on the moon,
    Cheese not included.
*/
#include <bits/stdc++.h>

#define endl '\n'
typedef long long ll;

using namespace std;

void solve(){
    long long x;
    cin >> x;

    long long M = 1LL << 60;
    long long a = M + x;
    long long b = M;

    cout << a << ' ' << b << '\n';
}


int main() {
    // Always chasing after that full moon glow
    // Warning: May cause howling at unusual times.
    #ifdef ONLINEJUDGE
       clock_t tStart = clock();
       freopen("input.txt","r",stdin), freopen("output.txt","w",stdout);
    #endif
    
    // Speed has never killed anyone ;)
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T = 1;
    // scanf("%d",&T);
    cin >> T;
    while(T--) solve();

    #ifdef ONLINEJUDGE
     fprintf(stderr, "\n>> Runtime: %.10fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
    #endif
    return 0;
}

The MEX of a prefix only increases when you add the exact number that was previously missing. This means if $$$m_i \gt m_{i-1}$$$, you have no choice: the current element $$$a_i$$$ must be exactly $$$m_{i-1}$$$.

If $$$m_i = m_{i-1}$$$, the new element did not change the MEX. This gives you a "free" slot at index $$$i$$$. You can place numbers here to prepare for future MEX increases, or just put a very large number that won't affect anything.

For the final MEX to be $$$m_n$$$, every single number from $$$0$$$ to $$$m_n - 1$$$ must be present somewhere in the array. Identify which of these numbers weren't already placed during the forced increases, and put them into your available "free" slots.

To reconstruct the array, we can make decisions step-by-step by comparing the current MEX $$$m_i$$$ with the previous MEX $$$m_{i-1}$$$ (assume $$$m_0 = 0$$$).

1. Handle the forced placements:

• If $$$m_i \lt m_{i-1}$$$, it's impossible (output -1), because the MEX can never decrease.
• If $$$m_i \gt m_{i-1}$$$, you are forced to set $$$a_i = m_{i-1}$$$. Keep track of the fact that you have now placed the number $$$m_{i-1}$$$.
• If $$$m_i == m_{i-1}$$$, record index $$$i$$$ as a "free" slot.

1. Fill in the missing requirements: Look at the final MEX value, $$$m_n$$$. For this to be the MEX, the numbers $$$0, 1, 2, \dots, m_n - 1$$$ must all exist in your array. Collect any of these numbers that haven't been placed yet.

2. Assign to free slots:Assign the missing numbers to your recorded "free" slots. If you have more missing numbers than free slots, output -1. For any leftover free slots that don't need a specific number, fill them with a "safe" value that won't interfere with the MEX, such as $$$n+1$$$.

3. Verify the construction: Because placing missing numbers into early free slots might accidentally increase the MEX too soon, you must do a final sanity check. Simulate the MEX calculation on your newly constructed array a. If the resulting prefix MEX array exactly matches the given array m, output your array a. Otherwise, output -1.

/*
    Going back to the essence.

    Just another day on the moon,
    Cheese not included.
*/
#include <bits/stdc++.h>

#define endl '\n'
typedef long long ll;

using namespace std;

void solve(){
    int n;
    cin >> n;

    vector<int> m(n + 1);

    for (int i = 1 ; i <= n ; ++i) {
        cin >> m[i];
    }

    vector<int> a(n + 1, -1);
    vector<int> free;
    set<int> st;

    m[0] = 0;
    for (int i = 1 ; i <= n ; ++i) {
        if (m[i] > m[i - 1]) {
            a[i] = m[i - 1];
            st.insert(m[i - 1]);
        } else if (m[i] == m[i - 1]) {
            free.push_back(i);
        } else {
            cout << -1 << '\n';
            return;
        }
    }

    vector<int> tmp;
    for (int i = 0 ; i < m[n] ; ++i) {
        if (st.find(i) == st.end()) {
            tmp.push_back(i);
        }
    }

    if (tmp.size() > free.size()) {
        cout << -1 << '\n';
        return;
    }

    for (int i = 0 ; i < (int) tmp.size() ; ++i) {
        a[free[i]] = tmp[i];
    }

    for (int i = tmp.size() ; i < (int) free.size() ; ++i) {
        a[free[i]] = n + 1;
    }

    vector<int> freq(n + 2, 0);
    int mex = 0;
    bool flag = true;

    for (int i = 1 ; i <= n ; ++i) {
        if (a[i] <= n + 1) ++freq[a[i]];
        while (freq[mex]) ++mex;
        if (mex != m[i]) {
            flag = false;
            break;
        }
    }

    if (!flag) {
        cout << -1 << '\n';
    } else {
        for (int i = 1 ; i <= n ; ++i) {
            cout << a[i] << (i == n ? "" : " ");
        }
        cout << '\n';
    }
}


int main() {
    // Always chasing after that full moon glow
    // Warning: May cause howling at unusual times.
    #ifdef ONLINEJUDGE
       clock_t tStart = clock();
       freopen("input.txt","r",stdin), freopen("output.txt","w",stdout);
    #endif
    
    // Speed has never killed anyone ;)
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T = 1;
    // scanf("%d",&T);
    cin >> T;
    while(T--) solve();

    #ifdef ONLINEJUDGE
     fprintf(stderr, "\n>> Runtime: %.10fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
    #endif
    return 0;
}