제출 #14089

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
14089		paulsohn	버블 정렬 (OJUZ10_bubblesort)	C++98	100 / 100	91 ms	7840 KiB

bubblesort

#include<cstdio>
#include<vector>
#include<algorithm>
#define B 131072
using namespace std;

int N,K;

struct key{
	int n, k, o;
	key(){}
	key(int n){this->n=n; k=0; o=0;}
} inp[100010];

int kw[100010], bit[262144];
vector<key> pk, npk;

bool ocmp(key a, key b){ return a.o<b.o; }
bool ncmp(key a, key b){ return a.n<b.n; }

int getsum(int x, int y){ //[x,y]의 합을 구한다
	if(x==y) return bit[x];
	if(x>y) return 0;
	int sum=0,X=x>>1,Y=y>>1;
	if(x&1){ ++X; sum+=bit[x]; }
	if(!(y&1)){ --Y; sum+=bit[y]; }
	return sum+getsum(X,Y);
}

void add(int x){
	while(x){ ++bit[x]; x>>=1; }
}

int main(){
	int i,j,l,r;
	scanf("%d%d",&N,&K);
	for(i=0;i<N;++i){ scanf("%d",&inp[i].n); inp[i].o=i; }
	sort(inp,inp+N,ncmp);
	for(i=0;i<N;++i){ inp[i].k=i; kw[i]=inp[i].n; }
	sort(inp,inp+N,ocmp);

	for(i=0;i<N;++i){
		if(getsum(B+inp[i].k+1,B+N-1)<K){
            pk.push_back(inp[i]);
            npk.push_back(key(0));
		}
		else npk.push_back(inp[i]);
		add(B+inp[i].k);
	}
	sort(pk.begin(),pk.end(),ncmp);
	for(i=K,j=0;i<npk.size();++i){
        if(npk[i].n) printf("%d ",npk[i].n);
        else{ printf("%d ", pk[j].n); ++j; }
	}
	for(;j<pk.size();++j) printf("%d ",pk[j].n);


}

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