acwing113. 特殊排序

记录交互题这个东西

class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> res;
        res.push_back(1);
        for(int i=2;i <= N;i++){
            int l=0,r=res.size()-1;
            while(l<=r){
                int mid =(l+r)/2;
                if(compare(res[mid],i)) l = mid + 1;
                else    r = mid - 1;
            }
            res.push_back(i);
            for(int j=res.size()-2;j>r;j--) swap(res[j],res[j + 1]);
        }
        return res;
    }
};