<p>Given an array <code>nums</code> with <code>n</code> objects colored red, white, or blue, sort them <strong><a href="https://en.wikipedia.org/wiki/In-place_algorithm" target="_blank">in-place</a> </strong>so that objects of the same color are adjacent, with the colors in the order red, white, and blue.</p>

<p>We will use the integers <code>0</code>, <code>1</code>, and <code>2</code> to represent the color red, white, and blue, respectively.</p>

<p>You must solve this problem without using the library&#39;s sort function.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,0,2,1,1,0]
<strong>Output:</strong> [0,0,1,1,2,2]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,0,1]
<strong>Output:</strong> [0,1,2]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == nums.length</code></li>
	<li><code>1 &lt;= n &lt;= 300</code></li>
	<li><code>nums[i]</code> is either <code>0</code>, <code>1</code>, or <code>2</code>.</li>
</ul>

<p>&nbsp;</p>
<p><strong>Follow up:</strong>&nbsp;Could you come up with a one-pass algorithm using only&nbsp;constant extra space?</p>

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

static const bool Booster = [](){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return true;
}();

void parse_input_and_solve(std::ofstream& out, std::string& s) {
    s.erase(s.begin());
    s.pop_back();
    int l = 0, r = s.length() - 1, it = 0;
    while (it <= r) {
        if (s[it] == '0') {
            std::swap(s[it], s[l]);
            it += 2;
            l += 2;
        } else if (s[it] == '2') {
            std::swap(s[it], s[r]);
            r -= 2;
        } else {
            it += 2;
        }
    }
    out << "[" << s << "]\n";
}

bool Solve = [](){
    std::ofstream out("user.out");
    for (std::string s; std::getline(std::cin, s);) {
        parse_input_and_solve(out, s);
    }
    out.flush();
    exit(0);
    return true;
}();

class Solution {
public:
    void quickSort(std::vector<int>& nums, int low, int high) {
        if (low < high) {
            int i = low, j = high;
            int pivot = nums[low];
            while (i < j) {
                while (i < high && nums[i] <= pivot) ++i;
                while (j > low && nums[j] > pivot) --j;
                if (i < j) std::swap(nums[i], nums[j]);
            }
            std::swap(nums[low], nums[j]);
            quickSort(nums, low, j - 1);
            quickSort(nums, j + 1, high);
        }
    }

    void sortColors(std::vector<int>& nums) {
        quickSort(nums, 0, nums.size() - 1);
    }
};

auto init = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 'c';
}();
7500