oj.uz

Submission #14196

# Submission time Handle Problem Language Result Execution time Memory
14196 2015-05-03T14:38:59 Z dohyun0324 버블 정렬 (OJUZ10_bubblesort) C++
100 / 100
 110 ms 35856 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 35856 KB Output is correct
2 Correct 0 ms 35856 KB Output is correct
3 Correct 0 ms 35856 KB Output is correct
4 Correct 0 ms 35856 KB Output is correct
5 Correct 0 ms 35856 KB Output is correct
6 Correct 0 ms 35856 KB Output is correct
7 Correct 0 ms 35856 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 35856 KB Output is correct
2 Correct 0 ms 35856 KB Output is correct
3 Correct 0 ms 35856 KB Output is correct
4 Correct 0 ms 35856 KB Output is correct
5 Correct 0 ms 35856 KB Output is correct
6 Correct 0 ms 35856 KB Output is correct
7 Correct 0 ms 35856 KB Output is correct
8 Correct 5 ms 35856 KB Output is correct
9 Correct 0 ms 35856 KB Output is correct
10 Correct 0 ms 35856 KB Output is correct

Subtask #3
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 35856 KB Output is correct
2 Correct 70 ms 35856 KB Output is correct
3 Correct 105 ms 35856 KB Output is correct
4 Correct 53 ms 35856 KB Output is correct
5 Correct 39 ms 35856 KB Output is correct
6 Correct 96 ms 35856 KB Output is correct
7 Correct 108 ms 35856 KB Output is correct
8 Correct 96 ms 35856 KB Output is correct
9 Correct 55 ms 35856 KB Output is correct
10 Correct 60 ms 35856 KB Output is correct
11 Correct 101 ms 35856 KB Output is correct
12 Correct 55 ms 35856 KB Output is correct
13 Correct 63 ms 35856 KB Output is correct
14 Correct 37 ms 35856 KB Output is correct
15 Correct 66 ms 35856 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 35856 KB Output is correct
2 Correct 43 ms 35856 KB Output is correct
3 Correct 35 ms 35856 KB Output is correct
4 Correct 64 ms 35856 KB Output is correct
5 Correct 95 ms 35856 KB Output is correct
6 Correct 69 ms 35856 KB Output is correct
7 Correct 58 ms 35856 KB Output is correct
8 Correct 102 ms 35856 KB Output is correct
9 Correct 56 ms 35856 KB Output is correct
10 Correct 68 ms 35856 KB Output is correct
11 Correct 80 ms 35856 KB Output is correct
12 Correct 61 ms 35856 KB Output is correct
13 Correct 110 ms 35856 KB Output is correct
14 Correct 95 ms 35856 KB Output is correct
15 Correct 104 ms 35856 KB Output is correct