oj.uz

답안 #15743

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
15743 2015-07-19T10:52:14 Z cki86201 버블 정렬 (OJUZ10_bubblesort) C++
100 / 100
 111 ms 3556 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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