class Solution {
public:
    int minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut)
    {
        // Sorting the cuts in descending order to start from the largest piece

        // Counters for horizontal and vertical pieces
        // Variable to accumulate the minimum cost

        // Loop until we have processed all possible cuts
        while ()
        {
            // Compare the current largest horizontal cut with the current largest vertical cut
            if ()
            {
                // Add the cost of the horizontal cut multiplied by the number of vertical pieces + 1
            }
            else
            {
                // Add the cost of the vertical cut multiplied by the number of horizontal pieces + 1
            }
        }

        // If there are remaining horizontal cuts, add their costs
        while ()
        {

        }

        // If there are remaining vertical cuts, add their costs
        while ()
        {

        }

        // Return the accumulated minimum cost
    }
};

class Solution {
public:
    int minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut)
    {
        sort(horizontalCut.begin(), horizontalCut.end(), greater<int>());
        sort(verticalCut.begin(), verticalCut.end(), greater<int>());

        int hPieces = 0, vPieces = 0;
        int minCost = 0;

        while (hPieces < m - 1 && vPieces < n - 1)
        {
            if (horizontalCut[hPieces] > verticalCut[vPieces])
            {
                minCost += horizontalCut[hPieces++] * (vPieces + 1);
            }
            else
            {
                minCost += verticalCut[vPieces++] * (hPieces + 1);
            }
        }

        while (hPieces < m - 1)
        {
            minCost += horizontalCut[hPieces++] * (vPieces + 1);
        }

        while (vPieces < n - 1)
        {
            minCost += verticalCut[vPieces++] * (hPieces + 1);
        }
        return minCost;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* modifiedList(vector<int>& nums, ListNode* head)
    {
        // Create an unordered set from the input vector nums for quick lookup
        // Create a dummy node to serve as the new list's head
        // Initialize a pointer to the dummy node for constructing the new list
        // Initialize a pointer to traverse the original list

        // Traverse the original list
        while ()
        {
            // If the current node's value is not in the set, add it to the new list
            if ()
            {
                // Create a new node with the current node's value and link it to the new list
                // Move the prev pointer to the newly created node
            }
            // Move to the next node in the original list

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* modifiedList(vector<int>& nums, ListNode* head)
    {
        unordered_set<int> st(nums.begin(), nums.end());

        ListNode* dummy = new ListNode();
        ListNode* prev = dummy;
        ListNode* cur = head;

        while (cur)
        {
            if (!st.count(cur->val))
            {
                prev->next = new ListNode(cur->val);
                prev = prev->next;
            }
            cur = cur->next;
        }
        return dummy->next;
    }
};

class Solution {
public:
    string getSmallestString(string s)
    {
        // Iterate through the string from the beginning to the second last character
        for ()
        {
            // Check if both current and next characters have the same parity (both even or both odd)
            // and if the current character is greater than the next character
            if ()
            {
                // Swap the current character with the next one
                // Exit the loop after the first swap
            }
        }
        // Return the modified string
    }
};

class Solution {
public:
    string getSmallestString(string s)
    {
        for (int i = 0; i < s.size() - 1; ++i)
        {
            if (s[i] % 2 == s[i + 1] % 2 && s[i] > s[i + 1])
            {
                swap(s[i], s[i + 1]); break;
            }
        }
        return s;
    }
};

#define ll long long

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int k)
    {
        unordered_map<int, ll> map;
        ll res = 0;

        for (int x : nums)
        {
            unordered_map<int, long long> map2;
            for (auto& [y, count] : map)
            {
                map2[y & x] += count;
            }
            map2[x] += 1;
            map = map2;
            res += map[k];
        }
        return res;
    }
};

class Solution {
public:
    int numberOfAlternatingGroups(vector<int>& colors, int k)
    {
        for (int i = 0; i < k - 1; ++i)
        {
            colors.push_back(colors[i]);
        }

        int res = 0;

        // cnt 用來記錄長度是否達到 k
        int cnt = 1;

        for (int i = 1; i < colors.size(); ++i)
        {
            // 如果是交錯的格子，則 cnt++
            if (colors[i] != colors[i - 1])
            {
                ++cnt;
            }
            else
            {
                // 如果不是交錯的格子，則 reset cnt= 1
                cnt = 1;
            }
            // 如果 cnt 達到 k，則結果 + 1
            if (cnt >= k) ++res;
        }
        return res;
    }
};

#define ll long long
class Solution {
public:
    long long maximumPoints(vector<int>& enemyEnergies, int currentEnergy)
    {
        sort(enemyEnergies.begin(), enemyEnergies.end());
        int n = enemyEnergies.size();

        if (currentEnergy < enemyEnergies[0]) return 0;

        ll availableEngergy = currentEnergy;
        for (int j = n - 1; j > 0; --j)
        {
            availableEngergy += enemyEnergies[j];
        }
        return availableEngergy / enemyEnergies[0];
    }
};

class Solution {
public:
    int numberOfAlternatingGroups(vector<int>& colors)
    {
        int n = colors.size();
        for (int i = 0; i < n; ++i)
        {
            colors.push_back(colors[i]);
        }

        int cnt = 0;
        for (int i = 0; i < n; ++i)
        {
            if (colors[i] == colors[i + 2] && colors[i] != colors[i + 1])
            {
                ++cnt;
            }
        }
        return cnt;

    }
};

/*
 * @lc app=leetcode id=3175 lang=cpp
 *
 * [3175] Find The First Player to win K Games in a Row
 *
 * https://leetcode.com/problems/find-the-first-player-to-win-k-games-in-a-row/description/
 *
 * algorithms
 * Medium (39.39%)
 * Likes:    127
 * Dislikes: 15
 * Total Accepted:    33.6K
 * Total Submissions: 85.4K
 * Testcase Example:  '[4,2,6,3,9]\n2'
 *
 * A competition consists of n players numbered from 0 to n - 1.
 *
 * You are given an integer array skills of size n and a positive integer k,
 * where skills[i] is the skill level of player i. All integers in skills are
 * unique.
 *
 * All players are standing in a queue in order from player 0 to player n - 1.
 *
 * The competition process is as follows:
 *
 *
 * The first two players in the queue play a game, and the player with the
 * higher skill level wins.
 * After the game, the winner stays at the beginning of the queue, and the
 * loser goes to the end of it.
 *
 *
 * The winner of the competition is the first player who wins k games in a
 * row.
 *
 * Return the initial index of the winning player.
 *
 *
 * Example 1:
 *
 *
 * Input: skills = [4,2,6,3,9], k = 2
 *
 * Output: 2
 *
 * Explanation:
 *
 * Initially, the queue of players is [0,1,2,3,4]. The following process
 * happens:
 *
 *
 * Players 0 and 1 play a game, since the skill of player 0 is higher than that
 * of player 1, player 0 wins. The resulting queue is [0,2,3,4,1].
 * Players 0 and 2 play a game, since the skill of player 2 is higher than that
 * of player 0, player 2 wins. The resulting queue is [2,3,4,1,0].
 * Players 2 and 3 play a game, since the skill of player 2 is higher than that
 * of player 3, player 2 wins. The resulting queue is [2,4,1,0,3].
 *
 *
 * Player 2 won k = 2 games in a row, so the winner is player 2.
 *
 *
 * Example 2:
 *
 *
 * Input: skills = [2,5,4], k = 3
 *
 * Output: 1
 *
 * Explanation:
 *
 * Initially, the queue of players is [0,1,2]. The following process
 * happens:
 *
 *
 * Players 0 and 1 play a game, since the skill of player 1 is higher than that
 * of player 0, player 1 wins. The resulting queue is [1,2,0].
 * Players 1 and 2 play a game, since the skill of player 1 is higher than that
 * of player 2, player 1 wins. The resulting queue is [1,0,2].
 * Players 1 and 0 play a game, since the skill of player 1 is higher than that
 * of player 0, player 1 wins. The resulting queue is [1,2,0].
 *
 *
 * Player 1 won k = 3 games in a row, so the winner is player 1.
 *
 *
 *
 * Constraints:
 *
 *
 * n == skills.length
 * 2 <= n <= 10^5
 * 1 <= k <= 10^9
 * 1 <= skills[i] <= 10^6
 * All integers in skills are unique.
 *
 *
 */

// @lc code=start
class Solution {
public:
    int findWinningPlayer(vector<int>& skills, int k) {
        int winner = 0, winCount = 0;
        for (int i = 1; i < skills.size(); i++) {
            if (skills[winner] > skills[i]) {
                winCount++;
            } else {
                winner = i;
                winCount = 1;
            }
            if (winCount == k) return winner;
        }
        return winner;
    }
};
// @lc code=end

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* insertGreatestCommonDivisors(ListNode* head)
    {
        if (!head->next) return head;

        ListNode* node1 = head;
        ListNode* node2 = head->next;
        while (node2)
        {
            int gcdVal = gcd(node1->val, node2->val);
            ListNode* gcdNode = new ListNode(gcdVal);

            node1->next = gcdNode;
            gcdNode->next = node2;

            node1 = node2;
            node2 = node2->next;
        }
        return head;
    }
};