#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
using namespace std;
struct Point{
int x;
int y;
};
struct compare_functor : public binary_function<bool,Point,Point>
{
bool operator ()(const Point &lhs, const Point &rhs) {
return lhs.x<rhs.x ;
}
};
int main() {
vector<Point> points;
for (int i = 0; i<100; i++) {
//ランダムな点を生成
Point pt = { rand() % (i+1), 0 };
auto pos=lower_bound(points.begin(),points.end(),pt,compare_functor()) ;
if(pos==points.end())
points.push_back(pt) ;
else
points.insert(pos,pt) ;
}
//要素を順に表示
for (int i = 0; i < 100; i++) {
cout << points[i].x << endl;
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8c3RkaW8uaD4KI2luY2x1ZGUgPGFsZ29yaXRobT4KCgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKc3RydWN0IFBvaW50ewoJaW50IHg7CglpbnQgeTsKfTsKCnN0cnVjdCBjb21wYXJlX2Z1bmN0b3IgOiBwdWJsaWMgYmluYXJ5X2Z1bmN0aW9uPGJvb2wsUG9pbnQsUG9pbnQ+CnsKCWJvb2wgb3BlcmF0b3IgKCkoY29uc3QgUG9pbnQgJmxocywgY29uc3QgUG9pbnQgJnJocykgewoJCXJldHVybiBsaHMueDxyaHMueCA7Cgl9Cn07CgppbnQgbWFpbigpIHsKCXZlY3RvcjxQb2ludD4gcG9pbnRzOwoJZm9yIChpbnQgaSA9IDA7IGk8MTAwOyBpKyspIHsKCQkvL+ODqeODs+ODgOODoOOBqueCueOCkueUn+aIkAoJCVBvaW50IHB0ID0geyByYW5kKCkgJSAoaSsxKSwgMCB9OwoJCWF1dG8gcG9zPWxvd2VyX2JvdW5kKHBvaW50cy5iZWdpbigpLHBvaW50cy5lbmQoKSxwdCxjb21wYXJlX2Z1bmN0b3IoKSkgOwoJCWlmKHBvcz09cG9pbnRzLmVuZCgpKQoJCSAgcG9pbnRzLnB1c2hfYmFjayhwdCkgOwoJCWVsc2UKCQkgIHBvaW50cy5pbnNlcnQocG9zLHB0KSA7Cgl9CgoJLy/opoHntKDjgpLpoIbjgavooajnpLoKCWZvciAoaW50IGkgPSAwOyBpIDwgMTAwOyBpKyspIHsKCQljb3V0IDw8IHBvaW50c1tpXS54IDw8IGVuZGw7Cgl9CgoJcmV0dXJuIDA7Cgp9