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;
}

Look at the bit positions where $$$a$$$ and $$$b$$$ are different. No matter what bit you choose for $$$c$$$ ($$$0$$$ or $$$1$$$), it will increase the number of bits of either $$$c \oplus a$$$ or $$$c \oplus b$$$ by exactly $$$1$$$. Based on this, when is the problem completely impossible to solve?

To maximize any binary number, you must prioritize the highest bits. A $$$1$$$ in a higher position is worth more than 1s in all the positions below it combined. You should build $$$c$$$ from left to right, what is the best way to do that?

Before adding a $$$1$$$ to your answer, make sure you can afford it. You must have enough of your limit $$$k$$$ left over to pay for the unavoidable differences waiting for you in the remaining bits.

Because we want the largest number, the greedy approach to fill out the bits is optimal, a $$$1$$$ in a higher position is worth more than all the 1s in the lower positions combined, we should build the number c bit by bit, starting from the highest bit (bit 59) down to the lowest bit (bit 0), always trying to place a $$$1$$$ if it is "safe" to do so.

To know if placing a $$$1$$$ is "safe," we have to make sure we don't exceed our limit $$$k$$$ for the number of set bits (1s) in both $$$c \oplus a$$$ and $$$c \oplus b$$$.

For every bit where $$$a$$$ and $$$b$$$ are different, $$$c$$$ will have to match one and disagree with the other. This means every difference forces us to add exactly $$$1$$$ to either the total of $$$c \oplus a$$$ or $$$c \oplus b$$$.

If the total number of differences is greater than $$$2 * k$$$, it is completely impossible to keep both totals under $$$k$$$. In this case, we stop and print $$$-1$$$ (Think of $$$k$$$ as your maximum penalty limit. You are allowed at most $$$k$$$ penalties for $$$a$$$, and at most $$$k$$$ penalties for $$$b$$$)

/*
    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;

const long long MOD = 1e9 + 7;

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

    long long diff = a ^ b;
    int rem = __builtin_popcountll(diff);

    if (rem > k + k) {
        cout << -1 << '\n';
        return;
    }

    long long c = 0;
    long long ca = 0, cb = 0;

    for (int bita, bitb, nca, ncb, i = 59 ; i >= 0 ; --i) {
        bita = (a >> i) & 1;
        bitb = (b >> i) & 1;

        if (bita != bitb) {
            --rem;
        }

        nca = ca + (bita == 0);
        ncb = cb + (bitb == 0);

        int mnmx = max({nca, ncb, (nca + ncb + rem + 1) / 2});
        if (mnmx <= k) {
            c |= (1LL << i);
            ca = nca;
            cb = ncb;
        } else {
            ca += (bita == 1);
            cb += (bitb == 1);
        }
    }

    cout << (c % MOD) << '\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;
}

mod=10**9+7
def pow_mod(x, n):
    y = 1
    x = x % mod
    while n > 0:
        if n & 1:
            y = (y * x) % mod
        n >>= 1
        x = (x * x) % mod
    return y
 
for _ in range(int(input())):
    a,b,k=map(int,input().split())
    cnt=0
    for i in range(60):
        if (1<<i)&a!=b&(1<<i):cnt+=1
    a_cnt=0
    b_cnt=0
    on_bits=[]
    if cnt<=2*k:
        for i in range(59,-1,-1):
            if (1<<i)&a==(1<<i)&b==(1<<i):
                on_bits.append(i)
            elif (1<<i)&a==(1<<i)&b==0:
                if a_cnt+1<=k and b_cnt+1<=k and a_cnt+b_cnt+cnt+2<=2*k:
                    a_cnt+=1
                    b_cnt+=1
                    on_bits.append(i)
            elif (1<<i)&a==(1<<i) and b_cnt+1<=k:
                b_cnt+=1
                cnt-=1
                on_bits.append(i)
            elif (1<<i)&b==(1<<i) and a_cnt+1<=k:
                a_cnt+=1
                cnt-=1
                on_bits.append(i)
        ans=0
        for bit in on_bits:
            ans=(ans+pow_mod(2,bit))%mod
        print(ans)
 
    else:
        print(-1)

Let $$$R_i$$$ be the XOR sum of the $$$i$$$-th row, and $$$C_j$$$ be the XOR sum of the $$$j$$$-th column. The problem states that $$$A_{i,j} = R_i \oplus C_j$$$. What happens if you try to recalculate $$$R_i$$$ by plugging this formula back into the row sum?

Let $$$S$$$ be the XOR sum of all elements in the entire grid. Notice that $$$S = \bigoplus_{i=1}^n R_i = \bigoplus_{j=1}^m C_j$$$. How does $$$S$$$ relate to the equation you found in Hint 1?

When you XOR a variable with itself, it cancels out ($$$x \oplus x = 0$$$). Because of this, whether $$$n$$$ and $$$m$$$ are odd or even completely changes the behavior of your equations.

Let $$$R_i$$$ be the XOR sum of row $$$i$$$, and $$$C_j$$$ be the XOR sum of column $$$j$$$. The problem explicitly requires:

This means every single cell is just the XOR of its row's sum and its column's sum. Let's dig into the math of a single row. If we sum up all the elements in row $$$i$$$ using our new formula, we get:

Because $$$R_i$$$ is repeated $$$m$$$ times in this XOR sum, we can group it. We can also group the sum of all $$$C_j$$$, which represents the XOR sum of the entire grid (let's call this global sum $$$S$$$).

By doing the exact same logic vertically for a column $$$j$$$, we get:

From here, the problem beautifully shatters into four simple cases based on the parity of $$$n$$$ and $$$m$$$.

Case 1: $$$n$$$ is Even, $$$m$$$ is Even

If $$$m$$$ is even, $$$(m \bmod 2) = 0$$$. Our row equation becomes $$$R_i = 0 \oplus S \implies R_i = S$$$. This means every single row sum is exactly the same value, $$$S$$$. If every row sum is $$$S$$$, and there are an even number of rows ($$$n$$$), then the total grid sum $$$S$$$ is just $$$S$$$ XORed with itself $$$n$$$ times.

Since $$$S = 0$$$, this means all $$$R_i = 0$$$ and all $$$C_j = 0$$$. Therefore, $$$A_{i,j} = 0 \oplus 0 = 0$$$. Only the all-zero grid works. The answer is 1.

Case 2: $$$n$$$ is Odd, $$$m$$$ is Odd

If $$$m$$$ is odd, our row equation becomes $$$R_i = R_i \oplus S$$$. The only way this is possible is if $$$S = 0$$$.The same goes for the columns. This tells us the total grid XOR sum must be 0, which means $$$\bigoplus R_i = 0$$$ and $$$\bigoplus C_j = 0$$$. How many valid arrays of $$$R$$$ exist where they all XOR to 0? We can freely choose the first $$$n-1$$$ elements (each can be $$$0$$$ or $$$1$$$), and the final element is strictly forced in order to make the sum 0. That gives us $$$2^{n-1}$$$ choices for the rows. By the same logic, we have $$$2^{m-1}$$$ choices for the columns. Because $$$n$$$ and $$$m$$$ are odd, flipping all bits in $$$R$$$ and $$$C$$$ would change their total XOR sums (violating $$$S=0$$$), meaning every valid $$$(R, C)$$$ pair maps to a unique grid.

Result: $$$2^{n-1} \times 2^{m-1} =$$$ $$$2^{n+m-2}$$$.

Case 3: $$$n$$$ is Even, $$$m$$$ is Odd

From $$$m$$$ being odd, we again get $$$R_i = R_i \oplus S \implies S = 0$$$. But since $$$n$$$ is even, our column equation becomes $$$C_j = 0 \oplus S$$$. Since $$$S=0$$$, this means $$$C_j = 0$$$ for all columns.The columns are completely fixed at 0. The rows just need to XOR to $$$S=0$$$, giving us $$$2^{n-1}$$$ degrees of freedom.Result: $$$2^{n-1}$$$.

Case 4: $$$n$$$ is Odd, $$$m$$$ is Even

This is the exact mirror of Case 3. The rows are forced to be 0, and the columns have $$$m-1$$$ degrees of freedom.Result: $$$2^{m-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;

const long long MOD = 998244353;

long long bxp(long long a, long long b) {
    long long result = 1;
    while(b) {
        if (b&1)
            result = result*a%MOD;
        b >>= 1;
        a=a*a%MOD;
    }
    return result;
}

void solve(){
    long long n, m;

    cin >> n >> m;

    if (n%2 == 0 and m%2 == 0) {
        cout << 1 << endl;
        return;
    }

    if (n&1 and m&1) {
        cout << bxp((long long)2, n + m - 2) << '\n';
        return;
    }

    if (n%2 == 0 and m&1) {
        cout << bxp((long long)2, n - 1) << '\n';
        return;
    }

    if (n&1 and m%2 == 0) {
        cout << bxp((long long)2, m - 1) << '\n';
        return;
    }
}


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;
}

mod=998244353
def pow_mod(x, n):
    y = 1
    while n > 0:
        if n&1:
            y = (y * x) % mod
        n>>=1
        x=(x*x) % mod
    return y
def mul(x,y):
    return((x*y)%mod)
for _ in range(int(input())):
    a,b=map(int,input().split())
    if a%2 and b%2:
        print(mul(pow_mod(2,(a-1)),pow_mod(2,(b-1))))
    elif a%2:
        print(pow_mod(2,(b-1)))
    elif b%2:
        print(pow_mod(2,(a-1)))
    else:
        print(1)

Instead of working with perpendicular distances, think about the beam's width in terms of angles. For any specific vertex of the enemy's shape, what range of angles (relative to the origin) will cause the thick beam to touch it? You can use right-triangle trigonometry (specifically the arcsine function) to find this

Because the enemy is represented as a strictly convex polygon, the total range of angles where the beam intersects the polygon will be one continuous sweep. This means you just need to determine the absolute minimum and maximum hitting angles among all the individual vertices to find the polygon's total "vulnerable" angular interval.

The most frustrating part of this problem is dealing with angles that wrap around at $$$2\pi$$$ (or $$$360^\circ$$$). To make calculating the minimum and maximum angles easier, consider mathematically rotating the polygon's coordinates (e.g., by $$$90^\circ$$$ steps) until the entire shape sits cleanly in a range that doesn't cross the $$$0$$$ or $$$2\pi$$$ boundary

The core of the problem is determining the exact angular interval $$$[\theta_{min}, \theta_{max}]$$$ where the enemy polygon is vulnerable to the beam, and then calculating how much time the beam spends inside that interval over $$$t$$$ units of time.

Step 1: Calculate the Hit Interval for Each Vertex

For each vertex $$$(x_i, y_i)$$$ of the polygon:

• Calculate its distance from the origin: $$$r_i = \sqrt{x_i^2 + y_i^2}$$$.
• Calculate its base polar angle: $$$\alpha_i = \text{atan2}(y_i, x_i)$$$.
• Because the beam has a half-width of $$$d$$$, it will touch the vertex before the central ray reaches $$$\alpha_i$$$ and continue touching it after it passes. The angular half-width of this interaction is $$$\beta_i = \arcsin(d / r_i)$$$.
• Therefore, the beam hits this specific vertex when the central ray's angle is within the interval $$$[\alpha_i - \beta_i, \alpha_i + \beta_i]$$$.

Step 2: Find the Polygon's Total Hit Interval

Since the polygon is strictly convex and lies entirely outside the circle of radius $$$d$$$ around the origin, the beam's intersection with the whole shape is continuous. The total angular range where the polygon takes damage is simply bounded by the extreme angles of its vertices:

• $$$\theta_{min} = \min(\alpha_i - \beta_i)$$$
• $$$\theta_{max} = \max(\alpha_i + \beta_i)$$$

Step 3: Normalize the Coordinate System Standard angle functions (like atan2) wrap around at boundaries (usually $$$-\pi$$$ to $$$\pi$$$, or $$$0$$$ to $$$2\pi$$$). If the polygon straddles this boundary, a simple min/max calculation will yield an incorrect, massive interval.To fix this, you can check if the calculated interval $$$\theta_{max} - \theta_{min}$$$ is larger than $$$\pi$$$. If it is, the shape crosses the boundary. Iteratively rotate all vertices of the polygon by $$$90^\circ$$$ (swapping $$$x$$$ and $$$y$$$ and negating) and recalculate until the shape no longer crosses the wrap-around threshold.

Step 4: Calculate Total Damage

Once you have a clean interval $$$[\theta_{min}, \theta_{max}]$$$, calculate the damage based on the beam's rotation:

• Full Rotations: Moon rotates at $$$1$$$ radian per unit of time. Calculate the number of full $$$2\pi$$$ rotations the beam completes: $$$k = \lfloor t / 2\pi \rfloor$$$. Each full rotation deals $$$(\theta_{max} - \theta_{min})$$$ damage.
• Partial Rotation: After accounting for full rotations, you have a remaining sweep time $$$t_{rem} = t \pmod{2\pi}$$$.
• Overlap: Calculate the starting angle of the beam $$$\theta_{start} = \text{atan2}(y_0, x_0)$$$. Check the overlap between the remaining sweep interval $$$[\theta_{start}, \theta_{start} + t_{rem}]$$$ and the vulnerable interval $$$[\theta_{min}, \theta_{max}]$$$.
• Add the overlap time to the full rotation damage to get your final answer. (Make sure to account for cases where the partial sweep itself crosses the $$$2\pi$$$ boundary and wraps into the beginning of the vulnerable interval).

Rayo

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>	
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ld PI = acosl(-1);
const ll oo = 1e18 + 7;
const int MOD = 998244353;
const int N = 5e3 + 5;
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define read(v) for (auto& it : v) scanf("%d", &it);
#define readl(v) for (auto& it : v) scanf("%lld", &it);
#define print(v) for (auto it : v) printf("%d ", it); puts("");
#define printl(v) for (auto it : v) printf("%lld ", it); puts("");
void solve() {
	int n;
	ld x0, y0, d, t;
	scanf("%d %Lf %Lf %Lf %Lf", &n, &x0, &y0, &d, &t);
	vector<ld>x(n), y(n);
	for (int i = 0; i < n; i++)
		scanf("%Lf %Lf", &x[i], &y[i]);
	ld sumX = accumulate(all(x), 0.0L), sumY = accumulate(all(y), 0.0L);
	ld cen = atan2l(sumY, sumX);
	ld l = 0, r = 0;
	for (int i = 0; i < n; i++) {
		ld angle = atan2l(y[i], x[i]);
		while (angle < cen - PI)
			angle += (2.0 * PI);
		while (angle > cen + PI)
			angle -= (2.0 * PI);
		ld dis = sqrtl(x[i] * x[i] + y[i] * y[i]);
		ld val = asinl(d / dis);
		ld curL = angle - val, curR = angle + val;
		if (i == 0)
			l = curL, r = curR;
		else
			l = min(l, curL), r = max(r, curR);
	}
	ld a = atan2l(y0, x0);
	while (a < cen - PI)
		a += (2.0 * PI);
	while (a > cen + PI)
		a -= (2.0 * PI);
	ld b = a + t;
	ld mn = ceil((a - r) / (2.0 * PI)), mx = floor((b - l) / (2.0 * PI));
	ld ans = 0;
	for (ll i = mn; i <= mx; i++) {
		ld curL = l + i * (2.0 * PI), curR = r + i * (2.0 * PI);
		ld st = max(a, curL), en = min(b, curR);
		ans += max(0.0L, en - st);
	}
	printf("%.9Lf\n", ans);
}
int t = 1;
int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif
	//scanf("%d", &t);
	while (t--)
		solve();
}

MrMoon

/*
    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;
 
const long double pi = acosl(-1.0L);
const long double twopi = pi + pi;
const int N = 1e6 + 100;
 
int n, d;
long double t;
int x[N], y[N]; 
 
long double get_angle(long double x, long double y) {
    long double d = sqrtl(x * x + y * y);
    long double angle = acosl(x / d);
    if (y < 0) 
        angle = twopi - angle;
 
    return angle;
}
 
void rotate() {
    for (int i = 0 ; i <= n ; ++i) {
        swap(x[i], y[i]);
        x[i] = -x[i];
    }
}
 
long double unionLRLR(long double l, long double r, long double L, long double R) {
    long double st = max(l, L);
    long double en = min(r, R);
    if (st < en) return en - st;
    return 0.0L;
}
 
void solve(){
    cin >> n >> x[0] >> y[0] >> d >> t;
    
    for (int i = 1 ; i <= n ; ++i) {
        cin >> x[i] >> y[i];
    }
 
    long double mn, mx;
    
    while (true) {
        mn = 1e18;
        mx = -1e18;
        
        for (int i = 1 ; i <= n ; ++i) {
            long double length = sqrtl(1.0L * x[i] * x[i] + 1.0L * y[i] * y[i]);
            long double a1 = get_angle(x[i], y[i]);
            long double a2 = asinl((long double)d / length);
 
            mn = min(mn, a1 - a2);
            mx = max(mx, a1 + a2);
        }
 
        if (mn < 0 || mx >= twopi || mx - mn > pi) {
            rotate();
        } else {
            break;
        }
    }
 
    long long round = (long long) (t / twopi);
    t -= twopi * round;
 
    long double a = get_angle(x[0], y[0]);
    long double r = t + a;
    long double r2 = -1, ans = round * (mx - mn);
 
    if (r > twopi) {
        r2 = r - twopi;
        r = twopi;
    }
 
    ans += unionLRLR(a, r, mn, mx);
    if (r2 > -1) {
        ans += unionLRLR(0, r2, mn, mx);
    }
 
    cout << fixed << setprecision(12) << 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;
}

Instead of trying to eliminate identical adjacent pairs like 00 or 11, imagine applying a periodic transformation based on index parity. What happens if you reframe the goal so that opposite characters (01 or 10) become the ones that annihilate each other?

A 2 is not a rigid character; it can morph into whatever you need it to be. Think of 2s as a pool of adjustable resources that can balance out the disparities between your remaining 0s and 1s.

Once local cancellations settle, the minimum length of the string is fundamentally constrained by two things: how many excess majority characters you are left with after using all your wildcards, and the inherent parity of the final string's length.

The problem allows us to erase adjacent identical pairs (00 or 11). By analyzing the alternating nature of positions in the string, we can visualize the string through an adjusted lens where we track elements based on whether they sit at even or odd indices. This transforms the target annihilation rule: matching pairs are eliminated, which behaves like tracking the balance between two opposing types of elements (let's call them category $$$A$$$ and category $$$B$$$).

The character 2 serves as a flexible buffer. Because a 2 can dynamically turn into either a 0 or a 1, it acts as a universal balancer.

• When you encounter 2s, they can be spent to directly bridge the gap between an uneven count of category $$$A$$$ and category $$$B$$$ characters.
• Every 2 you have effectively reduces the absolute difference between your majorities and minorities by 1.

After accounting for all natural cancellations and leveraging every available 2 to neutralize the difference between the remaining counts:

• If you have an excess of majority characters even after exhausting all your 2s, the remaining answer is simply that absolute difference.
• If your 2s are more than enough to wipe out the difference, any leftover 2s will pair up and cancel each other out. Depending on whether that final leftover amount is even or odd, you will be left with either a minimum length of 0 or 1.

Rayo

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>	
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ld PI = acos(-1);
const ll oo = 1e18 + 7;
const int MOD = 998244353;
const int N = 2e5 + 5;
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define read(v) for (auto& it : v) scanf("%d", &it);
#define readl(v) for (auto& it : v) scanf("%lld", &it);
#define print(v) for (auto it : v) printf("%d ", it); puts("");
#define printl(v) for (auto it : v) printf("%lld ", it); puts("");
void solve() {
	string s;
	cin >> s;
	int n = s.size();
	int cnt = 0, a = 0, b = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == '2') {
			cnt++;
			continue;
		}
		if ((s[i] == '0' && i % 2 == 0) || (s[i] == '1' && i % 2))
			a++;
		else
			b++;
	}
	printf("%d\n", max(n % 2, abs(a - b) - cnt));
}
int t = 1;
int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif
	scanf("%d", &t);
	while (t--)
		solve();
}

MrMoon

/*
    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();

    for (int i = 0 ; i < n ; i += 2) {
        if (s[i] < '2')
            s[i] ^= 1;
    }

    int count[4] = {0, 0, 0, 0};
    string tmp;
    for (int i = 0 ; i < n ; ++i) {
        ++count[s[i] - '0'];
        if (tmp.empty() or tmp.back() == s[i]) {
            tmp += s[i];
        }

        if (s[i] == '2') {
            tmp="";
        } else if (!tmp.empty() and tmp.back() != s[i]) {
            --count[tmp.back() - '0'];
            --count[s[i] - '0'];
            tmp.pop_back();
        }
    }

    int mn = min(count[0], count[1]);
    int mx = max(count[0], count[1]);

    if (mx - mn >= count[2]) {
        cout << mx - mn - count[2] << '\n';
    } else {
        count[2] -= (mx - mn);
        cout << (count[2] & 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;
}

Rayo

Run!

A standard graph where nodes are just "stations" won't work because the cost of your next move depends heavily on which subway line you are currently riding. You need your graph's states to represent both the current station and the specific line you are on.

If a station has many intersecting lines, checking every possible line-to-line transfer individually will be too slow (quadratic time complexity). Look closely at the transfer cost formula: $$$B_X \cdot A_Y$$$. Does this remind you of a specific algebraic equation?

The total cost to transfer to a new line $$$Y$$$ at a given station can be written as an equation of a line: $$$y = mx + c$$$. Here, $$$m$$$ is the transfer-out coefficient ($$$B_X$$$) of the line you are leaving, $$$x$$$ is the transfer-in coefficient ($$$A_Y$$$) of the new line, and $$$c$$$ is the total travel time accumulated so far. You need a data structure that efficiently finds the minimum value among a set of linear functions

The core of the problem is finding the shortest path (minimum time) in a graph, which immediately suggests Dijkstra's algorithm. However, the graph is complex, and building it naively will result in a Time Limit Exceeded (TLE) error.

Redefining the Graph Nodes

Because transferring has a variable cost based on your current line, a node in our graph cannot just be "Station 5." It must be a combination of "Station 5 on Line 2." From any state, you have two types of possible movements

• Travel Forward: Move to the next station on the same line. The cost is simply the travel time $$$w$$$.
• Transfer Lines: Move to a different line at the exact same station. The cost is $$$B_X \cdot A_Y$$$.

Identifying the Bottleneck

If a popular station has 100 different subway lines passing through it, a naive Dijkstra would require you to calculate the transfer cost between all $$$100 \times 100$$$ pairs of lines. If you do this across the entire network, the number of edges explodes, making the algorithm too slow. We must optimize how we calculate transfers.

The Geometric Optimization (Li-Chao Tree / Convex Hull Trick)

Suppose you are at station $$$S$$$ and want to calculate the cheapest way to board line $$$Y$$$. You want to find an arrival line $$$X$$$ that minimizes the following total cost:$$$\text{Arrival Time on } X + (B_X \cdot A_Y)$$$

We can map this to the standard linear equation $$$y = mx + c$$$:

• $$$x$$$ (the variable): $$$A_Y$$$, the transfer-in coefficient of the line we want to board.
• $$$m$$$ (the slope): $$$B_X$$$, the transfer-out coefficient of the line we arrived on.
• $$$c$$$ (the y-intercept): The total time it took us to arrive at station $$$S$$$ on line $$$X$$$.

Instead of checking every line $$$X$$$ individually when trying to board line $$$Y$$$, we maintain a "collection of lines" for each station. Every time Dijkstra finds a new, optimal path to a station on a specific line, we add its linear equation (slope and intercept) to that station's collection.

By using a specialized data structure—specifically a Li-Chao Tree—we can query this collection of equations to instantly find out which one produces the minimum $$$y$$$-value for our specific $$$x$$$ ($$$A_Y$$$). This reduces the time complexity of checking transfers at a station from quadratic to logarithmic.

Putting it Together (Modified Dijkstra)

1. Initialize Dijkstra's algorithm starting at Station 1 with a cost of 0.
2. Maintain a separate Li-Chao tree for every station in the network.
3. When you pop a state (Station $$$S$$$, Line $$$X$$$) from the priority queue:
   • Travel: Relax the edge to the next station on Line $$$X$$$ and push it to the queue if it's a shorter path.
   • Update Transfers: Add the linear equation representing your arrival on Line $$$X$$$ to Station $$$S$$$'s Li-Chao tree.
   • Query Transfers: Use the Li-Chao tree to check if this newly updated collection of arrival lines offers a cheaper way to board other lines at Station $$$S$$$. If it does, push those new states to the priority queue.

4. Once the algorithm finishes, the shortest time to reach any given station is simply the minimum arrival time across all the different lines that pass through it.

MrMoon

/*
    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;
 
const long long N = 1e6 + 10;
 
long long n, k, p, a[N], b[N], now[N];
map<long long, pair<long long, long long>> nxt[N];
set<tuple<long long, long long, long long, bool>> st;
 
class station {
  std::vector<long long> line;
  std::vector<long long> dis[2];
  std::map<long long, long long> map;
  long long tot = 0;
  std::vector<long long> k;
  std::vector<long long> b;
  long long st;
 
  struct node {
    node* son[2];
    long long id;
    long long l, r, mid;
  }* root;
 
  long long calc(long long id, long long x) {
    if (id == 0) {
      return 1e18;
    }
    x = ::b[line[x - 1]];
    return k[id - 1] * x + b[id - 1];
  }
 
  bool better(long long a, long long b, long long x) {
    auto s1 = calc(a, x), s2 = calc(b, x);
    if (s1 == s2) return a > b;
    return s1 < s2;
  }
 
  void build(node* p, long long l, long long r) {
    p->son[0] = p->son[1] = nullptr;
    p->l = l, p->r = r, p->id = 0;
    p->mid = (p->l + p->r) >> 1;
    if (l == r) return;
    long long mid = (l + r) >> 1;
    build(p->son[0] = new node, l, mid), build(p->son[1] = new node, mid + 1, r);
  }
 
  void insert(node* p, long long l, long long r, long long id) {
    if (p == nullptr) {
      cerr << "IS NOT RIGHT" << endl;
      exit(1);
    }
    if (l <= p->l && p->r <= r) {
      if (better(p->id, id, p->l) && better(p->id, id, p->r)) return;
      if (better(id, p->id, p->l) && better(id, p->id, p->r)) return p->id = id, void();
      if (better(id, p->id, p->mid)) std::swap(id, p->id);
      if (better(id, p->id, p->l))
        insert(p->son[0], l, r, id);
      else
        insert(p->son[1], l, r, id);
      return;
    }
    if (p->son[0]->r >= l) insert(p->son[0], l, r, id);
    if (p->son[1]->l >= r) insert(p->son[1], l, r, id);
  }
 
  long long ask(node* p, long long x) {
    if (p->l == p->r) return calc(p->id, x);
    long long ans = calc(p->id, x);
    if (p->son[0]->r >= x) 
        ans = min(ans, ask(p->son[0], x));
    if (p->son[1]->l <= x) 
        ans = min(ans, ask(p->son[1], x));
    return ans;
  }
 
public:
  void push(long long line) { this->line.push_back(line); }
  void init(long long kk) {
    st = kk;
    std::sort(line.begin(), line.end(), [](long long i, long long j) {
      if (::b[i] == ::b[j]) return i < j;
      return ::b[i] < ::b[j];
    });
    dis[1] = dis[0] = std::vector<long long>(line.size(), 1e18);
    for (long long i = 0; i < line.size(); i++) {
      map[line[i]] = i;
    }
    build(root = new node, 1, line.size());
  }
  
  void upd(long long dis, long long k, bool flag) {
    this->dis[flag][k] = dis;
    if (flag) return;
    this->k.push_back(a[line[k]]);
    this->b.push_back(dis);
    insert(root, 1, line.size(), this->k.size());
  }
  
  const vector<long long>& Line() { return line; }
  long long id(long long k) { return map[k]; }
  long long Dis2(long long k) {
    if (k + 1 > line.size()) return 1e18;
    return ask(root, k + 1);
  }
  long long Dis(long long k, bool flag) {
    if (k >= dis[flag].size()) return 1e18;
    return dis[flag][k];
  }
} s[N];
 
bool record(long long dis, long long i, long long k, bool flag) {
  if (dis >= s[i].Dis(k, flag)) {
    return false;
    ;
  }
  st.erase({s[i].Dis(k, flag), i, k, flag});
  s[i].upd(dis, k, flag);
  st.insert({dis, i, k, flag});
  return true;
}
 
void dijkstra() {
  for (long long i = 0, t = s[1].Line().size(); i < t; i++) {
    record(0, 1, i, false);
  }
  while (!st.empty()) {
    auto [dis, u, k, flag] = *st.begin();
    st.erase(st.begin());
    long long line = s[u].Line()[k];
    if (flag) {
      now[u]++;
      record(dis, u, k, false);
      record(s[u].Dis2(k + 1), u, k + 1, true);
    } else {
      if (nxt[line].count(u)) {
        auto [v, w] = nxt[line][u];
        record(dis + w, v, s[v].id(line), false);
      }
      if (now[u] < s[u].Line().size()) record(s[u].Dis2(now[u]), u, now[u], true);
    }
  }
}
 
void solve() {
    cin >> n >> k;
    for (long long i = 1 ; i <= k ; ++i) {
        cin >> b[i];
    }
 
    for (long long i = 1 ; i <= k ; ++i) {
        cin >> a[i];
    }
 
 
    for (long long u, i = 1 ; i <= k ; ++i) {
        cin >> p >> u;
        s[u].push(i);
        for (long long w, v, j = 1 ; j < p ; ++j) {
            cin >> w >> v;
            nxt[i][u] = {v, w};
            u = v;
            s[v].push(i);
        }
    }
 
    for (long long i = 1 ; i <= n ;++i) {
        s[i].init(i);
    }
 
    dijkstra();
 
    long long ans;
    for (long long i = 2 ; i <= n ; ++i) {
        ans = 1e18;
        for (long long j = 0 , t = s[i].Line().size() ; j < t ; ++j) {
            ans = min(ans, s[i].Dis(j, false));
            ans = min(ans, s[i].Dis(j, true));
        }
        cout << ans << ' ';
    }
}
 
 
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;
}

Rayo

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>	
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ld PI = acos(-1);
const ll oo = 1e18 + 7;
const int MOD = 1e9 + 7;
const int N = 2e5 + 5;
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define read(v) for (auto& it : v) scanf("%d", &it);
#define readl(v) for (auto& it : v) scanf("%lld", &it);
#define print(v) for (auto it : v) printf("%d ", it); puts("");
#define printl(v) for (auto it : v) printf("%lld ", it); puts("");
const ll inf = 2e18;
struct Node {
	ll st, ln, w;
};
struct Line {
	ll m, c;
	ll eval(ll x) {
		return m * x + c;
	}
};
struct node {
	Line line;
	node* left = nullptr;
	node* right = nullptr;
	node(Line line) : line(line) {}
	void add_segment(Line nw, int l, int r, int L, int R) {
		if (l > r || r < L || l > R) return;
		int m = (l + 1 == r ? l : (l + r) / 2);
		if (l >= L and r <= R) {
			bool lef = nw.eval(l) < line.eval(l);
			bool mid = nw.eval(m) < line.eval(m);
			if (mid) swap(line, nw);
			if (l == r) return;
			if (lef != mid) {
				if (left == nullptr) left = new node(nw);
				else left->add_segment(nw, l, m, L, R);
			}
			else {
				if (right == nullptr) right = new node(nw);
				else right->add_segment(nw, m + 1, r, L, R);
			}
			return;
		}
		if (max(l, L) <= min(m, R)) {
			if (left == nullptr) left = new node({ 0, inf });
			left->add_segment(nw, l, m, L, R);
		}
		if (max(m + 1, L) <= min(r, R)) {
			if (right == nullptr) right = new node({ 0, inf });
			right->add_segment(nw, m + 1, r, L, R);
		}
	}
	ll query_segment(ll x, int l, int r, int L, int R) {
		if (l > r || r < L || l > R) return inf;
		int m = (l + 1 == r ? l : (l + r) / 2);
		if (l >= L and r <= R) {
			ll ans = line.eval(x);
			if (l < r) {
				if (x <= m && left != nullptr) ans = min(ans, left->query_segment(x, l, m, L, R));
				if (x > m && right != nullptr) ans = min(ans, right->query_segment(x, m + 1, r, L, R));
			}
			return ans;
		}
		ll ans = inf;
		if (max(l, L) <= min(m, R)) {
			if (left == nullptr) left = new node({ 0, inf });
			ans = min(ans, left->query_segment(x, l, m, L, R));
		}
		if (max(m + 1, L) <= min(r, R)) {
			if (right == nullptr) right = new node({ 0, inf });
			ans = min(ans, right->query_segment(x, m + 1, r, L, R));
		}
		return ans;
	}
};
struct LiChaoTree {
	int L, R;
	node* root;
	LiChaoTree() : L(1), R(1000005), root(nullptr) {}
	LiChaoTree(int L, int R) : L(L), R(R), root(nullptr) {}
	void add_line(Line line) {
		if (root == nullptr) root = new node({ 0, inf });
		root->add_segment(line, L, R, L, R);
	}
	void add_segment(Line line, int l, int r) {
		if (root == nullptr) root = new node({ 0, inf });
		root->add_segment(line, L, R, l, r);
	}
	ll query(ll x) {
		if (root == nullptr) return inf;
		return root->query_segment(x, L, R, L, R);
	}
	ll query_segment(ll x, int l, int r) {
		if (root == nullptr) return inf;
		return root->query_segment(x, l, r, L, R);
	}
};
void solve() {
	int n, k;
	if (scanf("%d %d", &n, &k) != 2) return;
	vector<int> a(k), b(k);
	read(a);
	read(b);
	vector<Node> val;
	vector<vector<int>> g(n);
	for (int i = 0; i < k; i++) {
		int p;
		scanf("%d", &p);
		for (int j = 0; j < p; j++) {
			ll x, w = -1;
			scanf("%lld", &x);
			x--;
			if (j < p - 1)
				scanf("%lld", &w);
			int sz = (int)val.size();
			g[x].push_back(sz);
			val.push_back({ x, (ll)i, w });
		}
	}
	for (int i = 0; i < n; i++)
		sort(all(g[i]), [&](int x, int y)
			{ return a[val[x].ln] > a[val[y].ln]; });
	int sz = (int)val.size();
	vector<ll> dis(sz + n, oo), curB(n, oo);
	vector<int> curD(n);
	vector<LiChaoTree> lcts(n);
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
	for (int i = 0; i < n; i++)
		curD[i] = (int)g[i].size() - 1;
	for (auto& v : g[0])
		dis[v] = 0, pq.push({ 0, v });
	while (!pq.empty()) {
		ll d = pq.top().first;
		int u = pq.top().second;
		pq.pop();
		if (d != dis[u])
			continue;
		if (u < sz) {
			ll s = val[u].st, l = val[u].ln;
			ll curDis = d + val[u].w;
			if (val[u].w != -1 && curDis < dis[u + 1]) {
				dis[u + 1] = curDis;
				pq.push({ dis[u + 1], u + 1 });
			}
			if (!s || b[l] >= curB[s])
				continue;
			curB[s] = b[l];
			lcts[s].add_line({ b[l], d });
			if (curD[s] >= 0) {
				int v = g[s][curD[s]];
				curDis = lcts[s].query(a[val[v].ln]);
				if (curDis < dis[sz + s]) {
					dis[sz + s] = curDis;
					pq.push({ curDis, sz + (int)s });
				}
			}
		}
		else {
			int s = u - sz;
			if (curD[s] < 0) {
				dis[u] = oo;
				continue;
			}
			dis[u] = oo;
			int v = g[s][curD[s]--];
			if (d < dis[v]) {
				dis[v] = d;
				pq.push({ dis[v], v });
			}
			if (curD[s] >= 0) {
				v = g[s][curD[s]];
				ll curDis = lcts[s].query(a[val[v].ln]);
				if (curDis < dis[u]) {
					dis[u] = curDis;
					pq.push({ curDis, u });
				}
			}
		}
	}
	for (int i = 1; i < n; i++) {
		ll ans = oo;
		for (auto& v : g[i])
			ans = min(ans, dis[v]);
		printf("%lld ", ans);
	}
	puts("");
}
int t = 1;
int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif
	//scanf("%d", &t);
	while (t--)
		solve();
}

The two types of robots don't play by the same rules. One type is severely restricted by the single Mond Tool, while the other just needs any empty workbench. Which group's schedule dictates the success of the whole operation?

When scheduling the special robots, you want to leave as much "breathing room" as possible for everything else. If a special robot is due at hour 5, scheduling it at hour 1 blocks a highly valuable early slot. Where is the optimal place to put it?

Once the exact hours for every special robot are locked in, the problem simplifies massively. You essentially have a timeline with a known number of empty workbenches per hour. How should you assign the remaining normal robots to these open slots?

To solve this problem, we have to recognize that we are dealing with two completely different resource constraints overlapping each other. We have workbenches (abundant) and the Mond Tool (extremely limited). Because they don't share the same rules, we cannot schedule all the robots at the same time.

conceptual solution broken down into a two-part strategy: Phase 1: The Bottleneck (Scheduling Special Robots) The Mond Tool is our ultimate bottleneck because we can only use it once per hour, regardless of how many empty workbenches we have. Therefore, the special robots dictate the entire schedule.

We want to schedule special robots as late as possible. Why? Because an early hour (like hour 1 or 2) is incredibly valuable. If a robot has a deadline of hour 100, we could build it at hour 1, but doing so steals that hour from a robot that might have a deadline of hour 2.

1. Isolate all special robots and sort them by their deadline, from largest to smallest.
2. Assign each robot to the absolute latest available hour that is less than or equal to its deadline.
3. If you are ever forced to assign a special robot to an hour of 0 or less (because all hours before its deadline are already taken by other special robots), then the schedule is impossible.

By doing this, we lock in the exact hours the Mond Tool will be used, while preserving the maximum number of early hours for the rest of the factory.

the Mond Tool is no longer a factor. We now have a fixed timeline of factory capacity. For any given hour, we know exactly how many workbenches are free: If a special robot is scheduled that hour, we have $$$s - 1$$$ workbenches available. If no special robot is scheduled, we have all $$$s$$$ workbenches available.

Normal robots don't care when they are built, as long as it's before their deadline. Since all available workbenches are identical to them, we just need to make sure the most urgent robots get built first.

1. Isolate all normal robots and sort them by their deadline, from smallest (most urgent) to largest.
2. Start a clock at hour 1.
3. Assign: Take the most urgent normal robot and assign it to an available workbench at the current hour. If the current hour has no more available workbenches, advance the clock to the next hour.
4. Before assigning a robot, check the clock. If the current hour is strictly greater than the robot's deadline, the factory has failed to meet the deadline. Output "no".

If you successfully assign every normal robot without the clock ever exceeding a deadline, the schedule is perfectly valid.

/*
    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 type;
    int s, n;
    cin >> s >> n;

    vector<int> a, b;
    for (int d, i = 1 ; i <= n ; ++i) {
        cin >> d >> type;
        (type[0] == 'y' ? a : b).push_back(d);
    }

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    set<int> st;
    int tmp = (int) 2e9;
    for (auto i = a.rbegin() ; i != a.rend() ; ++i) {
        if (*i < tmp) {
            st.insert(*i);
            tmp = *i - 1;
        } else {
            st.insert(tmp--);
        }
    }

    if (st.size() and *(st.begin()) <= 0) {
        cout << "no\n";
        return;
    }

    int current = 0, len = 0;
    for (auto d : b) {
        while(len == 0) {
            len = s - (st.find(++current) != st.end());
        }

        if (current > d) {
            cout << "no\n";
            return;
        }

        --len;
    }

    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;
}

import heapq
s,n=map(int,input().split())
arr=[]
for _ in range(n):
    curr=input().split()
    curr[0]=int(curr[0])
    arr.append(curr)
works=True
arr.sort(key=lambda x:x[0])
cnt_y=0
other=0
for i in range(n):
    if arr[i][1]=='y':cnt_y+=1
    else:other+=1
    if cnt_y>arr[i][0] or other+cnt_y>arr[i][0]*s:
        works=False
        break
print("yes" if works else "no")

With both the number of teams and matches capped at $$$100$$$, avoid overthinking. You don't need a fancy mathematical shortcut or a complex data structure. What is the most literal, step-by-step way you can mimic the coach's rules?

thee match results tell you who won, but the rules are entirely based on where they currently sit. Before evaluating any match, you must have a way to scan the current leaderboard and find the physical standing of both teams.

Think about what physically happens when you pull a book out of the middle of a tightly packed stack and place it somewhere else. Every book between the old spot and the new spot shifts exactly one position

When a problem has extremely small constraints ($$$n, m \le 100$$$), it isn't asking you to find a brilliant optimization; it is testing your ability to translate a set of physical, real-world rules exactly into logic.Think of the current standings as a physical wooden leaderboard on a wall.

We start by creating our leaderboard. Initially, the board is perfectly ordered, with Team 1 in the 1st slot, Team 2 in the 2nd slot, all the way down to Team $$$n$$$.

We must process every single match chronologically (arranging events in the exact order they happened, starting from the earliest time and moving forward to the latest). When a match result comes in (a winner and a loser), we cannot just look at their names. We have to scan our current leaderboard from top to bottom to find the exact slots where the winner and loser are currently standing.

Once we know their current ranks, we evaluate the coach's rules:

• The "No Upset" Rule: If the winner's current slot is higher on the board than the loser's current slot, the result matches expectations. We touch nothing and move on to the next match.

• The "Upset" Rule: If the winner is currently sitting below the loser, a shakeup happens. We execute a three-step shift:

  1. We conceptually pull the loser's name off the board, creating an empty gap.
  2. Every single team sitting between the loser's old spot and the winner's spot slides up exactly one rank to fill the vacuum above them.
  3. Because the winner just slid up, they leave behind a new gap at their original starting position. We drop the loser into this exact gap.

the maximum number of teams is $$$100$$$, and there are at most $$$100$$$ matches, the maximum number of shifts your program will ever have to execute is roughly $$$100 \times 100 = 10,000$$$ operations.

/*
    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;

const int N = 110;
int n, m, x, y, winner, loser, pos_win, pos_lose, ranking[N];

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

    for (int i = 1 ; i <= n ; ++i) {
        ranking[i] = i;
    }

    while (m--) {
        scanf("%d %d", &winner, &loser);
        pos_win = -1;
        pos_lose = -1;

        for (int i = 1 ; i <= n ; ++i) {
            if (ranking[i] == winner) pos_win = i;
            if (ranking[i] == loser) pos_lose = i;
        }

        if (pos_win > pos_lose) {
            for (int i = pos_lose ; i < pos_win ; ++i) {
                ranking[i] = ranking[i + 1];
            }

            ranking[pos_win] = loser;
        }
    }

    for (int i = 1 ; i <= n ; ++i) {
        printf("%d ", ranking[i]);
    }
    printf("\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;
}

n,m=map(int,input().split())
arr=[i for i in range(1,n+1)]
for _ in range(m):
    u,v=map(int,input().split())
    if arr.index(u)>arr.index(v):
       arr.remove(v) 
       arr.insert(arr.index(u)+1,v)
print(*arr)

Finding the exact median of a shifting array is incredibly difficult. Instead, reframe the question. Ask a "Yes/No" question: Can we achieve a median of at least $$$X$$$? If the array has $$$n$$$ elements (and $$$n$$$ is odd), the median is $$$\ge X$$$ if and only if at least $$$\frac{n+1}{2}$$$ elements in the array are $$$\ge X$$$.

you can achieve a median of at least 10, you can definitely achieve a median of at least 9. If you cannot achieve a median of 20, you definitely cannot achieve 21.

For a fixed guess $$$X$$$, you want to maximize the number of face-up cards that are $$$\ge X$$$. If you flip a card, its contribution to your "$$$\ge X$$$" count might go up by 1, go down by 1, or not change at all. Since you can only flip a contiguous subsegment, how can you find the subsegment that gives you the highest net gain?

we have to stop trying to calculate the median directly after a flip. Sorting the array every time we consider a flip would be way too slow.

Instead of asking "What is the maximum median?", we guess a number $$$X$$$ and ask, "Is it possible to make the median at least $$$X$$$?"Because the answer to this question is monotonic (a sequence of Yes, Yes, Yes... No, No, No), we can binary search the optimal median between the smallest and largest possible numbers on the cards (from $$$1$$$ to $$$10^9$$$).

For a specific guess $$$X$$$, how do we know if it's possible to make the median at least $$$X$$$? For an array of $$$n$$$ odd elements, the median will be at least $$$X$$$ as long as at least $$$\frac{n+1}{2}$$$ of the face-up cards are $$$\ge X$$$. So, our goal for this specific guess $$$X$$$ is simply to maximize the count of face-up cards that meet or exceed $$$X$$$. We don't care what the actual numbers are anymore; we only care if a number is a "winner" ($$$\ge X$$$) or a "loser" ($$$ \lt X$$$).

Before doing any flips, we count how many face-up cards are already winners. Now, we want to choose exactly one continuous segment of cards to flip to boost our winner count as much as possible. Let's evaluate the "net gain" of flipping each individual card:

1. If the face-up side is a loser, but the face-down side is a winner, flipping this card gives us a net gain of $$$+1$$$ winner.If the face-up side is a winner, but the face-down side is a loser, flipping it hurts us. The net gain is $$$-1$$$.
2. If both sides are winners, or both sides are losers, flipping changes nothing. The net gain is $$$0$$$.

By calculating this net gain ($$$+1$$$, $$$-1$$$, or $$$0$$$) for every single card in a row, the problem transforms into finding the contiguous segment of cards that yields the highest total sum.

This is the exact definition of the Maximum Subarray Sum problem, which can be solved in a single pass using Kadane's Algorithm. We just walk down the row, keeping a running tally of the current segment's gain. If the tally ever drops below zero, we throw it away and start a new segment, keeping track of the highest peak we ever reach.

/*
    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;

const int N = 3e5 + 10;
long long n, l, r, mx, mid, med, sum, current, a[N], b[N];

bool check(long long x) {
    current = 0;
    for (int i = 1 ; i <= n ; ++i) {
        current += (a[i] >= x);
    }

    mx = 0, sum = 0;
    for (int now, i = 1 ; i <= n ; ++i) {
        now = (b[i] >= x) - (a[i] >= x);
        sum += now;
        sum = max(0ll, sum);
        mx = max(mx, sum);
    }
    return current + mx >= med;
}

void solve(){
    cin >> n;
    for (int i = 1 ; i <= n ; ++i) {
        cin >> a[i] >> b[i];
    }

    med = (n >> 1) + 1;

    l = 1, r = 1e9;
    while (l < r) {
        mid = (l + r + 1) >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }

    cout << l << '\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;
}

code is from the one and only zei20241012

#include <bits/stdc++.h>
#define ll long long
const int MOD = 1e9 + 7;
using namespace std;

bool check(int mid, int n, vector<int> &a, vector<int> &b, vector<int> &prefix, vector<int> &tb, vector<int> &ta)
{
    int sum = 0;
    for (int i = 0; i < n; i++)
    {

        if (a[i] >= mid)
        {
            ta[i] = 1;
        }
        else
        {
            ta[i] = -1;
        }

        if (b[i] >= mid)
        {
            tb[i] = 1;
        }
        else
        {
            tb[i] = -1;
        }

        sum += ta[i];
        prefix[0] = 0;
        prefix[i + 1] = prefix[i] + (tb[i] - ta[i]);
    }

    int mxd = 0, mnp = 0;
    for (int i = 1; i <= n; i++)
    {
        int curr = prefix[i] - mnp;
        mxd = max(mxd, curr);
        mnp = min(mnp, prefix[i]);
    }

    if (sum + mxd > 0)
    {
        return true;
    }
    else
        return false;
}

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

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

    vector<int> ta(n), tb(n), prefix(n + 1, 0);

    int l = 0, r = 1e9, ans = 0;
    while (l <= r)
    {
        int mid = l + (r - l) / 2;
        if (check(mid, n, a, b, prefix, tb, ta))
        {
            ans = mid;
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }

    cout << ans << endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    //  cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}
/* ⢀⡶⠶⢦⣄⠀⠀⠀⠀⠀⣴⠟⠛⢧⣠⣶⣿⠻⣆⠀⠀⠀
⠀⠀⢸⠁⡟⠦⠌⠛⠉⠉⠉⢹⠇⢠⣶⣼⣷⣞⢙⣧⣿⡀⠀⠀
⠀⠀⢸⣤⠃⠀⠀⠀⠀ ⠀ ⣿⠀⠈⢻⡃⠀⢸⡿⡄⠈⣿⠀⠀
⠀⠀⣼⠁⠀⠀⠀⠀⠀⠀⠀ ⠘⠷⠖⠛⠛⠛⢿⡗⢋⣴⠏⠀⠀
⠀⠀⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⠛⢻⡀⢀⣀
⡶⠾⣷⠆⠀⠀⣤⡀⠀⠀⠀⠀⠀⠀⠀⢀⣤⡀⠀⠐⢺⡟⠉⠉
⢀⣤⢿⡦⠀⠀⠛⠃⠀⠀⢠⢶⣄⠀⠀⠈⠛⠀⠀⠀⣺⠓⠟⡀
⠀⠀⣠⡿⣖⡀⣀⣀⡀⠀⠈⠉⠉⠀⠀⣀⣀⣀⠀⣲⣯⣄⠀⠀
⠀⠀⠁⣴⠟⠉⠁⠀⠉⠛⢦⡀⢀⡴⠛⠉⠁⠈⠙⠻⣄⠀⠁⠀
⠀⢠⣼⠃⠀⠀⠀⠀⠀⠀⠀⠿⠋⠀⠀⠀⠀⠀⠀⠀⠹⣦⠀⠀
⠀⠈⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⠀⠀
⠀⢠⠿⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣰⠷⠀⠀
⠀⠀⠘⢻⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡼⠃⠀⠀⠀
⠀⠀⠀⠀⠈⠻⢦⣄⠀⠀⠀⠀⠀⠀⠀⠀⣠⡴⠛⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠉⠛⠶⣄⡀⢀⣠⠶⠋⠁⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠛⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀*/

def check(number):
    cnt=0
    new=[]
    for i in range(n):
        if cards[i][0]>=number:
            cnt+=1
            if cards[i][1]>=number:
                new.append(0)
            else:
                new.append(-1)
        elif cards[i][1]>=number:
            new.append(1)
        else:
            new.append(0)
    sm_mx=0
    mx=0
    for i in range(n):
        sm_mx+=new[i]
        sm_mx=max(sm_mx,0)
        mx=max(mx,sm_mx)
    if (cnt+mx>=((n+1)//2)):
        return(True)
n=int(input())
cards=[]
all=[]
first=[]
for i in range(n):
    cards.append(list(map(int,input().split())))
    first.append(cards[-1][0])
    all.append(cards[-1][0])
    all.append(cards[-1][1])
all.sort()
first.sort()
ans=first[n//2]
l=1
r=10**9
while l<=r:
    mid=(l+r)//2
    if check(mid):
        l=mid+1
        ans=mid
    else:
        r=mid-1
for i in range(len(all)-1,-1,-1):
    if all[i]<=ans:
        print(all[i])
        break

The phrasing "maximum and minimum possible scores" means you aren't dealing with probability or hidden information. Imagine you get to physically arrange both Moon's and Luna's decks to force the absolute best-case scenario, and then you do it again to force the absolute worst-case scenario.

Every round ends in a $$$+1$$$, a $$$0$$$, or a $$$-1$$$. If you are trying to maximize the score, you have a strict priority list: what matches should you form first? Once those are exhausted, what is your backup plan to protect your score?

Because the total number of cards is equal ($$$n$$$) and every card must be played, any card you cannot use to secure a win or force a tie has only one possible fate.

This is fundamentally a bipartite matching problem, but because of the strict $$$+1, 0, -1$$$ scoring system, we can solve it perfectly using a Greedy Algorithm.

We need to calculate two completely separate scenarios: one where the deck is stacked entirely in Moon's favor, and one where it is stacked entirely against him.

If we want to maximize Moon's score, we must be incredibly greedy. We process the matchups in a strict hierarchy of importance.

1. Priority 1: Secure all wins ($$$+1$$$). We want Moon to win as much as physically possible. We pair Moon's Stones with Luna's Blades, Moon's Blades with Luna's Scrolls, and Moon's Scrolls with Luna's Stones. We take the maximum overlap for each of these three matchups.
2. Priority 2: Damage Control ($$$0$$$). Once Moon can no longer win, we must prevent him from losing. How? By forcing ties. We look at Moon's remaining cards and Luna's remaining cards, and we pair identical items together (Stones vs. Stones, etc.). This yields $$$0$$$ points, which is better than losing.
3. Priority 3: Accept Defeat ($$$-1$$$). Because $$$n$$$ rounds must be played, any cards remaining in Moon's hand after Priorities 1 and 2 are completely exhausted are physically incapable of winning or tying. They are forced to lose. We simply subtract these unavoidable losses from our score.

To find the minimum possible score, we completely flip the script. Imagine Luna is now dictating the matchups to ruin Moon's score. She uses the exact same greedy logic, but in reverse.

1. Priority 1: Force all losses ($$$-1$$$). Luna aggressively pairs her winning cards against Moon's losing cards. Every time she does this, Moon's score drops.
2. Priority 2: Force ties ($$$0$$$). When Luna runs out of guaranteed wins, she forces ties to prevent Moon from scoring any positive points.
3. Priority 3: Accept Moon's Wins ($$$+1$$$). Whatever cards Luna has left over are fundamentally incapable of beating or tying Moon's remaining hand. These become Moon's unavoidable wins, which are added back to the score.

/*
    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, r1, s1, p1, r2, s2, p2;
    cin >> n >> r1 >> s1 >> p1 >> r2 >> s2 >> p2;

    int moon = 0, luna = 0;

    // win;
    moon += min(s1, p2);
    moon += min(r1, s2);
    moon += min(p1, r2);

    int r1tmp = r1, s1tmp = s1, p1tmp = p1;
    int r2tmp = r2, s2tmp = s2, p2tmp = p2;

    s1tmp -= min(s1, p2);
    p2tmp -= min(s1, p2);

    r1tmp -= min(r1, s2);
    s2tmp -= min(r1, s2);

    p1tmp -= min(p1, r2);
    r2tmp -= min(p1, r2);

    // tie;
    int e = min(s1tmp, s2tmp);
    s1tmp -= e;
    s2tmp -= e;

    e = min(p1tmp, p2tmp);
    p1tmp -= e;
    p2tmp -= e;

    e = min(r1tmp, r2tmp);
    r1tmp -= e;
    r2tmp -= e;

    // lose;
    e = min(s2tmp, p1tmp);
    moon -= e;
    moon -= min(r2tmp, s1tmp);
    moon -= min(p2tmp, r1tmp);

    //lose;
    luna -= min(s2, p1);
    luna -= min(r2, s1);
    luna -= min(p2, r1);

    e = min(s2, p1);
    s2 -= e;
    p1 -= e;

    e = min(r2, s1);
    r2 -= e;
    s1 -= e;

    e = min(p2, r1);
    p2 -= e;
    r1 -= e;

    // tie;
    e = min(r1, r2);
    r1 -= e;
    r2 -= e;
    e = min(s1, s2);
    s1 -= e;
    s2 -= e;
    e = min(p1, p2);
    p1 -= e;
    p2 -= e;

    //win;
    luna += min(s1, p2);
    luna += min(r1, s2);
    luna += min(p1, r2);

    cout << moon << ' ' << luna << '\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;
}

:] write it and send it to me

A literal simulation (using a queue data structure and simulating turn-by-turn) seems obvious, but what happens if a person needs 100,000 units of time and Moon only processes 1 unit per turn? Simulating that would be way too slow. How can we skip to the end?

If Moon processes $$$M$$$ units of time per turn, and a person needs $$$R_i$$$ units total, you can calculate exactly how many times that person needs to visit the front of the queue to finish their request

If two different people both require exactly 3 visits to the front of the queue to finish their tasks, who will finish their 3rd visit first? Think about how their starting positions in the original line affect their position in later rounds.

Instead of asking when someone finishes in terms of absolute time, we should ask how many turns it takes them to finish.If Moon can process $$$M$$$ units of time per turn, a person requesting $$$R_i$$$ units of time will need to visit the desk $$$\lceil R_i / M \rceil$$$ times. (For example, if a person needs 11 units of time and Moon processes 5 units per turn, they need $$$11 / 5 \rightarrow 3$$$ total turns).By calculating this for every person, we instantly know their "exit round."

Once we know how many turns everyone needs, the exit order becomes obvious. Anyone who only needs 1 turn will completely leave the office before anyone who needs 2 turns. Anyone who needs 2 turns will leave before anyone who needs 3 turns.

Therefore, our primary sorting criteria is simple: order the people by the number of round trips they require, from smallest to largest.

What happens if two people need the exact same number of turns?

Imagine Alice is 2nd in the original line, and Bob is 5th. They both need exactly 3 turns.

1. In Round 1, Alice goes to the desk before Bob.

2. In Round 2, Alice goes to the desk before Bob.

3. In Round 3 (their final round), Alice will naturally go to the desk before Bob, meaning she exits the queue before him.

Because the queue is strictly First-In-First-Out for each round, the original starting positions are perfectly preserved among people on the same round. Therefore, our secondary sorting criteria (the tie-breaker) is simply their original position in the line.

/*
    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;
 
const int N = 1e6 + 10;
int n, m;
pair<int, int> a[N];
 
void solve(){
    cin >> n >> m;
 
    for (int x, i = 0 ; i < n ; ++i) {
        cin >> x;
        a[i] = {(x - 1)/m, i + 1};
    }
 
    sort(a, a + n);
    for (int i = 0 ; i < n ; ++i) 
        cout << a[i].second << ' ';
}
 
 
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;
}

import sys
from sys import stdin, stdout
input = lambda: sys.stdin.readline().rstrip()
print = stdout.write
n,m=map(int,input().split())
arr=list(map(int,input().split()))
for i in range(n):
    arr[i]=[(arr[i]+m-1)//m,i]
arr.sort()
for i in range(n):print(str(arr[i][1]+1)+' ')
print('\n')

The definition of MEX revolves entirely around the number 0. Since the grid must contain every number from 0 to $$$n \cdot m - 1$$$ exactly once, the number 0 can only physically exist in one single cell. What does this instantly tell you about the MEX of every other row and column?

Let's assume 0 is at intersection $$$(r, c)$$$. This means row $$$r$$$ and column $$$c$$$ are the only ones allowed to have a MEX greater than 0. But what happens if both row $$$r$$$ and column $$$c$$$ need a MEX strictly greater than 1? Where would the number 1 have to go to satisfy both?

If you can prove that the targets in arrays $$$a$$$ and $$$b$$$ are possible, the actual placement is straightforward. Once you satisfy the strict requirements for row $$$r$$$ and column $$$c$$$, how can you safely dump the remaining large numbers to avoid accidentally changing the MEX?

This isn't really a 2D grid problem; it's a logic puzzle about resource contention.

Because every number from 0 to $$$n \cdot m - 1$$$ appears exactly once, the number 0 appears exactly once.

Let's say we place it at cell $$$(r, c)$$$. If a row does not contain 0, its MEX is automatically 0. The same applies to columns. Because 0 is only in row $$$r$$$ and column $$$c$$$, every other row and column is forced to have a MEX of 0.

This immediately gives us our first massive shortcut: array $$$a$$$ can have at most one non-zero value, and array $$$b$$$ can have at most one non-zero value. If the input asks for multiple rows or columns to have a MEX $$$ \gt 0$$$, it is outright impossible. We can immediately output "No".

Assuming the arrays are valid so far, let's look at the two non-zero targets: row $$$r$$$ needs a MEX of $$$a_r$$$, and column $$$c$$$ needs a MEX of $$$b_c$$$. If both $$$a_r \gt 1$$$ and $$$b_c \gt 1$$$, it means both the row and the column require the number 1 to be present.

• If we place 1 somewhere in row $$$r$$$, it is now missing from column $$$c$$$, which caps column $$$c$$$'s MEX at 1 (failing the $$$b_c \gt 1$$$ requirement).
• If we place 1 somewhere in column $$$c$$$, it is missing from row $$$r$$$, capping row $$$r$$$'s MEX at 1.

The only way they could share the number 1 is if we placed it at their intersection $$$(r, c)$$$ — but that single cell is already occupied by 0! Because they cannot share the number 1, it is impossible for both lines to have a MEX greater than 1. this means $$$\min(a_r, b_c) = 1$$$. One line is allowed to have a large MEX, but the other must be strictly capped at 1. (Also, $$$a_r \le m$$$ and $$$b_c \le n$$$, since a line cannot have a MEX larger than its physical cell count).

If all these checks pass, the matrix is guaranteed to exist. Building it is just a matter of greedy placement:

1. Place 0 at the crosshair $$$(r, c)$$$.
2. Fulfill the Row: If $$$a_r \gt 1$$$, place $$$1, 2, \dots, a_r - 1$$$ into the available empty slots of row $$$r$$$.
3. Fulfill the Column: If $$$b_c \gt 1$$$, place $$$1, 2, \dots, b_c - 1$$$ into the empty slots of column $$$c$$$.
4. Now we must fill the rest of the grid with the remaining unused numbers. Our only danger is accidentally placing the "forbidden" number $$$a_r$$$ into row $$$r$$$, or $$$b_c$$$ into column $$$c$$$. To be completely safe, fill the remaining empty slots of row $$$r$$$ and column $$$c$$$ using the absolute largest numbers available (like $$$n \cdot m - 1$$$). Dump the remaining smaller numbers into the rest of the grid.

Because we satisfied the specific MEX requirements first and padded the active row/col with numbers far too large to affect the MEX, the grid will be perfectly valid.

/*
    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, m;
    cin >> n >> m;

    vector<int> a(n), b(m);
    int r = 0, c = 0, counta = 0, countb = 0;

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

    for (int i = 0 ; i < m ; ++i) {
        cin >> b[i];
        if (b[i]) {
            c = i;
            ++countb;
        }
    }

    if (counta != 1 or countb != 1 or a[r] > m or b[c] > n or min(a[r], b[c]) != 1) {
        cout << "No\n";
        return;
    }

    if ((n == 1 and a[r] != m) or (m == 1 and b[c] != n)) {
        cout << "No\n";
        return;
    }

    cout << "Yes\n";
    vector<vector<int>> C(n, vector<int>(m, -1));
    C[r][c] = 0;
    int current = 1;

    if (a[r] > 1) {
        for (int i = 0 ; i < m and current < a[r] ; ++i) 
            if (i != c)
                C[r][i] = current++;

        if (n > 1) C[(r + 1)%n][c] = current++;
    } else if (b[c] > 1) {
        for (int i = 0 ; i < n and current < b[c] ; ++i)
            if (i != r)
                C[i][c] = current++;
        if (m > 1) C[r][(c + 1)%m] = current++;
    } else if (n > 1 and m > 1) {
        C[(r + 1)%n][(c + 1)%m] = current++;
    }

    for (int i = 0 ; i < n ; ++i) {
        for (int j = 0 ; j < m ; ++j) {
            if (C[i][j] == -1) C[i][j] = current++;
            cout << C[i][j] << ' ';
        }
        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;
}

Write it and send it to me :D

when you can apply operations infinitely, you must always look for the property that never changes. When you flip the bits at both ends of an edge, how does the total count of '1's change?

Treat every bit index as a node and every available operation pair as an undirected edge connecting two nodes.

Because you can only flip bits connected by operations, changes are strictly confined to connected components within your graph. Combining this with your invariant, what must unconditionally be true about the target number of '1's in each component ?

First, we abstract the problem. The bits are our nodes, and the operations are undirected edges. Because operations can be chained together indefinitely, a bit can dynamically "interact" with any other bit as long as they reside within the same connected component of the graph.

Since Moon starts with a sequence of all zeros, the sum of '1's in any component is initially zero (which is an even number). Every time an operation is applied, two bits are flipped simultaneously. Let us observe the outcomes:

• Flipping two '0's makes them both '1's. The sum increases by two.
• Flipping two '1's makes them both '0's. The sum decreases by two.
• Flipping one '1' and one '0' swaps their states. The sum remains exactly the same.

Notice the unyielding rule here: the total number of '1's in any connected component will always change by an even amount. Therefore, the parity of the sum of '1's in any isolated component is strictly invariant. Because it starts even, it must always remain even.

Because of this invariant, we can seamlessly pair up and shift '1's along the edges of our graph to create or destroy any even amount of '1's.

If a connected component in the target sequence requires an odd number of '1's, it is impossible to reach, meaning the overall answer is "NO". If every single connected component in the target sequence requires an even number of '1's, the configuration is achievable, and the answer is "YES".

code is from the one and only Mohammad-Najjar

#include <iostream>
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <iomanip>
using namespace std;
#define int long long
#define float long double
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define all(x) x.begin(), x.end()

vector<vector<int>> graph(100005);
vector<int> a;
set<int> seen;
int dfs(int node) {
    if (seen.count(node)) return 0;
    seen.insert(node);
    
    int ans = a[node] == 1;
    
    for (int neighbor : graph[node]) {
        // cout << "Node: " << node << ' ' << neighbor << '\n';
        ans += dfs(neighbor);
    }
    return ans;
}

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

    a.assign(n, 0); for (auto &x : a) cin >> x;

    // graph.assign(n);

    int q; cin >> q;
    while (q--) {
        int l, r; cin >> l >> r;

        l--; r--;

        graph[l].push_back(r);
        graph[r].push_back(l);
    }

    // for (int i = 0; i<n; i++) {
    //     for (int j = 0; j<graph[i].size(); j++)
    //     cout << i << ' ' <<  graph[i][j] << '\n';
    // }

    for (int i = 0; i<n; i++) {
        if (dfs(i) % 2 != 0) {
            no;
            return;
        }
    }

    yes;
}

int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

/*
    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;
 
const int N = 1e5 + 10;
int n, m, b[N], l[N], r[N], fa[N], sum[N];
 
int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}
 
void join(int u, int v) {
    int x = find(u);
    int y = find(v);
 
    if (x != y) {
        fa[x] = y;
        b[y] += b[x];
    }
}
 
void solve(){
    cin >> n;
 
    for (int i = 1 ; i <= n ; ++i) fa[i] = i;
    for (int i = 1 ; i <= n ; ++i) cin >> b[i];
 
    cin >> m;
    for (int i = 1 ; i <= m ; ++i) {
        cin >> l[i] >> r[i];
        join(l[i], r[i]);
    }
 
    bool flag = false;
 
    for (int i = 1 ; i <= n ; ++i) {
        if (find(i) == i) {
            if (b[i] & 1) {
                flag = true;
                break;
            }
        }
    }
 
    cout << (flag ? "No" : "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;
}

n=int(input())
arr=list(map(int,input().split()))
works=True
adj=[[] for i in range(n+1)]
for _ in range(int(input())):
    a,b=map(int,input().split())
    adj[a].append(b)
    adj[b].append(a)
visited=[0 for i in range(n+1)]
for i in range(1,n+1):
    if visited[i]==0:
        cnt=0
        stck=[i]
        while stck:
            parent=stck.pop()
            visited[parent]=1
            cnt+=arr[parent-1]
            for child in adj[parent]:
                if visited[child]==0:
                    visited[child]=1
                    stck.append(child)
        if cnt%2:
            works=False
print("Yes" if works else "No")