代码

#include<cstdio>
using namespace std;
#define int unsigned int
inline int read()
{
    int x=0,w=1;
    char ch=0;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*w;
}
inline void write(int x) 
{
    if(x<0) 
    { 
        x=-x;
        putchar('-');
    }
    if(x>=10) write(x/10);
    putchar((x%10)^48);
}
int w[100000005],cnt;
void swap(int &x,int &y)
{
    x^=y;
    y^=x;
    x^=y;
}
int top()
{
    return w[1];
}
void _repair1(int x)
{
    const int y=x>>1;
    if(y<1||w[x]>w[y]) return;
    swap(w[x],w[y]);
    _repair1(y);
}
void insert(int x)
{
    w[++cnt]=x;
    _repair1(cnt);
}
void _repair2(int x)
{
    int y=x<<1;
    if(y>cnt) return;
    if(y+1<=cnt) y=w[y]<w[y+1]?y:y+1;
    if(w[y]<w[x])
    {
        swap(w[x],w[y]);
        _repair2(y);
    }
}
void pop()
{
    swap(w[1],w[cnt--]);
    _repair2(1);
}
int a[100000005];
void sort()
{
    const int n=100000000;
    for(int i=1;i<=n;i++)
    {
        int x=read();
        insert(x);
    }
    for(int i=1;i<=n;i++) a[i]=top(),putchar(' '),pop();
    return 0;
}

评测结果