#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Compare
{
public:
static int num;
Compare()
{
num++;
}
Compare(const Compare& compare)
{
num++;
}
~Compare()
{
}
bool operator() (int v1, int v2)
{
return v1 < v2;
}
};
int Compare::num = 0;
int main()
{
vector<int> mas;
int size = 10000000;
for( int k = 1; k <= size; k++ )
{
mas.push_back( rand() );
}
sort( mas.begin(), mas.end(), Compare() );
float rate = (float)Compare::num/(float)size;
cout<<"rate="<<rate<<endl;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNsYXNzIENvbXBhcmUKewpwdWJsaWM6CgogICAgc3RhdGljIGludCBudW07CgogICAgQ29tcGFyZSgpCiAgICB7CiAgICAgIG51bSsrOwogICAgfQoKICAgIENvbXBhcmUoY29uc3QgQ29tcGFyZSYgY29tcGFyZSkKICAgIHsKICAgICAgbnVtKys7CiAgICB9CgogICAgfkNvbXBhcmUoKQogICAgewogICAgfQogIAogICAgYm9vbCBvcGVyYXRvcigpIChpbnQgdjEsIGludCB2MikKICAgIHsKICAgICAgcmV0dXJuIHYxIDwgdjI7CiAgICB9Cn07CmludCBDb21wYXJlOjpudW0gPSAwOwoKaW50IG1haW4oKQp7CiAgICB2ZWN0b3I8aW50PiBtYXM7CgogICAgaW50IHNpemUgPSAxMDAwMDAwMDsKICAgIGZvciggaW50IGsgPSAxOyBrIDw9IHNpemU7IGsrKyApCiAgICB7CiAgICAgICAgbWFzLnB1c2hfYmFjayggcmFuZCgpICk7CiAgICB9CgogICAgc29ydCggbWFzLmJlZ2luKCksIG1hcy5lbmQoKSwgQ29tcGFyZSgpICk7CgogICAgZmxvYXQgcmF0ZSA9IChmbG9hdClDb21wYXJlOjpudW0vKGZsb2F0KXNpemU7CgogICAgY291dDw8InJhdGU9Ijw8cmF0ZTw8ZW5kbDsKCiAgICByZXR1cm4gMDsKfQ==