Submission #19113

#	Time	Username	Problem	Language	Result	Execution time	Memory
19113		mindol	버블 정렬 (OJUZ10_bubblesort)	C++14	100 / 100	210 ms	6100 KiB

bubblesort

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

struct segtree
{
    int tree[1<<18],base=1<<17;
    void add(int place)
    {
        for(place+=base-1;place>=1;place>>=1)
            tree[place]++;
    }
    int rangeSum(int s,int e)
    {
        int sum=0;
        for(s+=base-1,e+=base-1;s<=e;s>>=1,e>>=1)
        {
            if(s&1) sum+=tree[s++];
            if(!(e&1)) sum+=tree[e--];
        }
        return sum;
    }
} p,q;

vector<int> cpr,z;
vector<pair<int,int>> v;
int a[100001];
int fin[100001];

int main()
{
    int n,k;
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        cpr.push_back(a[i]);
    }
    sort(cpr.begin(),cpr.end());
    for(int i=1;i<=n;i++)
    {
        a[i]=lower_bound(cpr.begin(),cpr.end(),a[i])-cpr.begin()+1;
        p.add(a[i]);

        int c=p.rangeSum(a[i]+1,n);
        if(k<=c) c=i-k;
        else c=i-c;
        v.push_back(make_pair(a[i],c));
    }
    sort(v.begin(),v.end());
    for(int i=0;i<n;i++)
    {
        int s=v[i].second,e=n,ans;
        while(s<=e)
        {
            int mid=(s+e)/2;
            int res=q.rangeSum(s,mid);
            if(res<mid-s+1)
                ans=mid, e=mid-1;
            else s=mid+1;
        }
        q.add(ans);
        fin[ans]=v[i].first;
    }
    for(int i=1;i<=n;i++)
        printf("%d ",cpr[fin[i]-1]);
    return 0;
}

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