Submission #13927

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
13927	2015-04-23T15:41:31 Z	model_code	버블 정렬 (OJUZ10_bubblesort)	C++	100 / 100	69 ms	3232 KB

bubblesort

#include<stdio.h>
#include<algorithm>
using namespace std;

struct nums {
	int num, nwid;
	bool operator< (const nums& c) const {
		if(num != c.num)return num<c.num;
		return nwid<c.nwid;
	}
}ba[100100];

int n, k;
int j2, itr[250100], dap[100100];

void upd(int num, int wd){
	int cnt=1;
	if(wd<0)wd=0;
	wd+=j2;
	while(1){
		if(itr[wd]==cnt){
			if(wd%2==1)wd++;
			else wd/=2, cnt*=2;
		}
		else{
			if(cnt==1)break;
			if(itr[wd*2]==cnt/2)wd=wd*2+1;
			else wd*=2;
			cnt/=2;
		}
	}
	dap[wd-j2]=num;
	for(;wd; wd/=2)itr[wd]++;
}

int main(){
	int i;
	scanf("%d%d", &n, &k);
	for(j2=1; j2<n; j2<<=1);
	for(i=0; i<n; i++){
		scanf("%d", &ba[i].num);
		ba[i].nwid=i;
	}
	sort(ba, ba+n);
	for(i=0; i<n; i++)upd(ba[i].num, ba[i].nwid-k);
	for(i=0; i<n; i++)printf("%d ", dap[i]);
	return 0;
}

Subtask #1

11.0 / 11.0

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

Subtask #2

23.0 / 23.0

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

Subtask #3

47.0 / 47.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	3232 KB	Output is correct
2	Correct	38 ms	3232 KB	Output is correct
3	Correct	41 ms	3232 KB	Output is correct
4	Correct	53 ms	3232 KB	Output is correct
5	Correct	43 ms	3232 KB	Output is correct
6	Correct	40 ms	3232 KB	Output is correct
7	Correct	60 ms	3232 KB	Output is correct
8	Correct	43 ms	3232 KB	Output is correct
9	Correct	40 ms	3232 KB	Output is correct
10	Correct	53 ms	3232 KB	Output is correct
11	Correct	58 ms	3232 KB	Output is correct
12	Correct	61 ms	3232 KB	Output is correct
13	Correct	54 ms	3232 KB	Output is correct
14	Correct	58 ms	3232 KB	Output is correct
15	Correct	54 ms	3232 KB	Output is correct

Subtask #4

19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	3232 KB	Output is correct
2	Correct	52 ms	3232 KB	Output is correct
3	Correct	41 ms	3232 KB	Output is correct
4	Correct	45 ms	3232 KB	Output is correct
5	Correct	40 ms	3232 KB	Output is correct
6	Correct	48 ms	3232 KB	Output is correct
7	Correct	40 ms	3232 KB	Output is correct
8	Correct	46 ms	3232 KB	Output is correct
9	Correct	42 ms	3232 KB	Output is correct
10	Correct	57 ms	3232 KB	Output is correct
11	Correct	64 ms	3232 KB	Output is correct
12	Correct	62 ms	3232 KB	Output is correct
13	Correct	54 ms	3232 KB	Output is correct
14	Correct	69 ms	3232 KB	Output is correct
15	Correct	53 ms	3232 KB	Output is correct