Submission #14089

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
14089	2015-04-30T08:47:18 Z	paulsohn	버블 정렬 (OJUZ10_bubblesort)	C++	100 / 100	91 ms	7840 KB

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.0 / 11.0

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

Subtask #2

23.0 / 23.0

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

Subtask #3

47.0 / 47.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	82 ms	7840 KB	Output is correct
2	Correct	61 ms	7072 KB	Output is correct
3	Correct	88 ms	7840 KB	Output is correct
4	Correct	78 ms	7840 KB	Output is correct
5	Correct	78 ms	6128 KB	Output is correct
6	Correct	29 ms	5004 KB	Output is correct
7	Correct	77 ms	6156 KB	Output is correct
8	Correct	76 ms	6108 KB	Output is correct
9	Correct	76 ms	7072 KB	Output is correct
10	Correct	82 ms	7840 KB	Output is correct
11	Correct	62 ms	7072 KB	Output is correct
12	Correct	61 ms	6176 KB	Output is correct
13	Correct	68 ms	6112 KB	Output is correct
14	Correct	80 ms	7840 KB	Output is correct
15	Correct	72 ms	7072 KB	Output is correct

Subtask #4

19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	66 ms	7072 KB	Output is correct
2	Correct	78 ms	7840 KB	Output is correct
3	Correct	83 ms	7072 KB	Output is correct
4	Correct	71 ms	6108 KB	Output is correct
5	Correct	77 ms	6156 KB	Output is correct
6	Correct	83 ms	7840 KB	Output is correct
7	Correct	78 ms	6128 KB	Output is correct
8	Correct	24 ms	5004 KB	Output is correct
9	Correct	87 ms	7840 KB	Output is correct
10	Correct	72 ms	7840 KB	Output is correct
11	Correct	54 ms	7072 KB	Output is correct
12	Correct	70 ms	6176 KB	Output is correct
13	Correct	60 ms	6112 KB	Output is correct
14	Correct	61 ms	7072 KB	Output is correct
15	Correct	91 ms	7840 KB	Output is correct