Submission #14196

#	Time	Username	Problem	Language	Result	Execution time	Memory
14196		dohyun0324	버블 정렬 (OJUZ10_bubblesort)	C++98	100 / 100	110 ms	35856 KiB

bubblesort

#include<stdio.h>
#include<algorithm>
#include<stdlib.h>
using namespace std;
int t,n,k,b[100010],tree[200010],nxt[21][200010],num[21][200010];
struct data{
    int x,p;
    bool operator<(const data&r)const{
        return x>r.x;
    }
}a[100010];
void update(int x){
    while(x<=t){
        tree[x]++;
        x+=x&(-x);
    }
}
int query(int x){
    int cnt=0;
    while(x){
        cnt+=tree[x];
        x-=x&(-x);
    }
    return cnt;
}
int func(){
    int i;
    for(i=1;i<=18;i++){
        if(rand()%2==0) break;
    }
    return i;
}
void update2(int p,int h,int pos)
{
    int i,x=1,c=0;
    for(i=20;i>=1;i--){
        while(c+num[i][x]<p && nxt[i][x]!=0) c+=num[i][x], x=nxt[i][x];
        if(i<=h){
            nxt[i][pos]=nxt[i][x]; nxt[i][x]=pos;
            num[i][pos]=c+num[i][x]-p+1; num[i][x]=num[i][x]-num[i][pos]+1;
        }
        else num[i][x]++;
    }
}
int main()
{
    int i,h,x=1,p;
    scanf("%d %d",&n,&k);
    for(i=1;i<=n;i++){scanf("%d",&a[i].x); a[i].p=i;}
    sort(a+1,a+n+1);
    for(t=1;t<=n;t*=2);
    for(i=1;i<=n;i++){
        b[i]=query(a[i].p);
        update(a[i].p);
    }
    for(i=k+1;i<=n;i++){
        p=max(0,b[i]-k);
        h=func();
        update2(p,h,i);
    }
    for(i=1;i<=n-k;i++){
        x=nxt[1][x];
        printf("%d ",a[x].x);
    }
    for(i=k;i>=1;i-- ) printf("%d ",a[i].x);
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 47 / 47
• Subtask 4: 19 / 19