#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int p1 = 0, p2 = 0, p3 = nums.size() - 1;
        while(p1 < p3) {
            while(p1 < p3 && nums[p1] == 0) p1++;
            while(p1 < p3 && nums[p3] == 2) p3--;
            if(p2 < p1) {
                p2 = p1;
            }
            if(nums[p1] == 1 && nums[p3] == 1) {
                while(p2 < p3 && nums[p2] == 1) p2++;
                if(p2 >= p3) break;
                nums[p2] == 0 ? swap(nums[p1++], nums[p2++]) : swap(nums[p3--], nums[p2++]);
            } else {
                swap(nums[p1], nums[p3]);
            }
        }
    }
};

int main()
{
    Solution obj;
    //int a[] = {2, 0, 2, 1, 1, 0};
    //vector<int>nums(a, a+6);
    //int b[] = {0, 0};
    //vector<int>nums(b, b+2);
    int c[10] = {1,2,2,2,2,0,0,0,1,1};
    vector<int>nums(c , c+10);
    obj.sortColors(nums);
    for(int i = 0; i < (int)nums.size(); ++i) {
        cout<<nums[i]<<endl;
    }
    return 0;
}