Submission #15743

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
15743	2015-07-19T10:52:14 Z	cki86201	버블 정렬 (OJUZ10_bubblesort)	C++	100 / 100	111 ms	3556 KB

bubblesort

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

typedef long long ll;
typedef pair<int,int> Pi;
#define X first
#define Y second

int p[100010], n, k, q[100010], per[100010], s[100010];

struct BIT{
	int r[100010];
	void update(int x){for(int i=x+1;i<=n;i+=(i&-i))r[i]++;}
	int read(int x){
		int ret = 0;
		for(int i=x+1;i;i-=(i&-i))ret += r[i];
		return ret;
	}
	void clear(){for(int i=1;i<=n;i++)r[i] = 0;}
}bit;

bool comp(const int &a, const int &b){return p[a] < p[b];}

int main(){
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++)scanf("%d",p+i);
	for(int i=0;i<n;i++)per[i] = i;
	stable_sort(per, per+n, comp);
	for(int i=0;i<n;i++){
		s[i] = max(per[i] - bit.read(per[i]) - k, 0);
		bit.update(per[i]);
	}
	bit.clear();
	for(int i=0;i<n;i++){
		int low=0, high=n-1, cor=0;
		while(low<=high){
			int mid = (low+high) / 2;
			if(s[i] <= mid - bit.read(mid))cor = mid, high = mid - 1;
			else low = mid + 1;
		}
		q[cor] = p[per[i]];
		bit.update(cor);
	}
	for(int i=0;i<n;i++)printf("%d ",q[i]);
	return 0;
}

Subtask #1

11.0 / 11.0

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

Subtask #2

23.0 / 23.0

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

Subtask #3

47.0 / 47.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	80 ms	3556 KB	Output is correct
2	Correct	95 ms	3556 KB	Output is correct
3	Correct	88 ms	3556 KB	Output is correct
4	Correct	111 ms	3556 KB	Output is correct
5	Correct	35 ms	3316 KB	Output is correct
6	Correct	80 ms	3556 KB	Output is correct
7	Correct	58 ms	3440 KB	Output is correct
8	Correct	104 ms	3556 KB	Output is correct
9	Correct	105 ms	3556 KB	Output is correct
10	Correct	78 ms	3556 KB	Output is correct
11	Correct	94 ms	3556 KB	Output is correct
12	Correct	73 ms	3476 KB	Output is correct
13	Correct	84 ms	3556 KB	Output is correct
14	Correct	76 ms	3512 KB	Output is correct
15	Correct	102 ms	3556 KB	Output is correct

Subtask #4

19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	108 ms	3556 KB	Output is correct
2	Correct	33 ms	3316 KB	Output is correct
3	Correct	79 ms	3556 KB	Output is correct
4	Correct	96 ms	3556 KB	Output is correct
5	Correct	86 ms	3556 KB	Output is correct
6	Correct	66 ms	3476 KB	Output is correct
7	Correct	101 ms	3556 KB	Output is correct
8	Correct	77 ms	3556 KB	Output is correct
9	Correct	78 ms	3512 KB	Output is correct
10	Correct	96 ms	3556 KB	Output is correct
11	Correct	54 ms	3440 KB	Output is correct
12	Correct	104 ms	3556 KB	Output is correct
13	Correct	85 ms	3556 KB	Output is correct
14	Correct	99 ms	3556 KB	Output is correct
15	Correct	78 ms	3556 KB	Output is correct