oj.uz

Submission #15740

# Submission time Handle Problem Language Result Execution time Memory
15740 2015-07-19T10:38:00 Z cki86201 버블 정렬 (OJUZ10_bubblesort) C++
0 / 100
 121 ms 3164 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;
	sort(per, per+n, comp);
	vector <int> v;
	for(int i=0;i<n;i++){
		if(i > 0 && p[per[i]] != p[per[i-1]]){
			for(int j=0;j<(int)v.size();j++)bit.update(per[v[j]]);
			v.clear();
		}
		s[i] = max(per[i] - bit.read(per[i]) - k, 0);
		v.push_back(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
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 3164 KB Output isn't correct
2 Incorrect 0 ms 3164 KB Output isn't correct
3 Correct 0 ms 3164 KB Output is correct
4 Incorrect 0 ms 3164 KB Output isn't correct
5 Incorrect 0 ms 3164 KB Output isn't correct
6 Incorrect 0 ms 3164 KB Output isn't correct
7 Incorrect 0 ms 3164 KB Output isn't correct

Subtask #2
0.0 / 23.0

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

Subtask #3
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 3164 KB Output isn't correct
2 Incorrect 97 ms 3164 KB Output isn't correct
3 Incorrect 57 ms 3164 KB Output isn't correct
4 Incorrect 90 ms 3164 KB Output isn't correct
5 Incorrect 96 ms 3164 KB Output isn't correct
6 Incorrect 104 ms 3164 KB Output isn't correct
7 Incorrect 80 ms 3164 KB Output isn't correct
8 Incorrect 100 ms 3164 KB Output isn't correct
9 Incorrect 79 ms 3164 KB Output isn't correct
10 Incorrect 83 ms 3164 KB Output isn't correct
11 Incorrect 121 ms 3164 KB Output isn't correct
12 Incorrect 105 ms 3164 KB Output isn't correct
13 Correct 85 ms 3164 KB Output is correct
14 Incorrect 117 ms 3164 KB Output isn't correct
15 Incorrect 103 ms 3164 KB Output isn't correct

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 110 ms 3164 KB Output isn't correct
2 Incorrect 82 ms 3164 KB Output isn't correct
3 Incorrect 107 ms 3164 KB Output isn't correct
4 Incorrect 97 ms 3164 KB Output isn't correct
5 Incorrect 100 ms 3164 KB Output isn't correct
6 Incorrect 82 ms 3164 KB Output isn't correct
7 Incorrect 82 ms 3164 KB Output isn't correct
8 Incorrect 97 ms 3164 KB Output isn't correct
9 Incorrect 72 ms 3164 KB Output isn't correct
10 Correct 82 ms 3164 KB Output is correct
11 Incorrect 88 ms 3164 KB Output isn't correct
12 Incorrect 105 ms 3164 KB Output isn't correct
13 Incorrect 90 ms 3164 KB Output isn't correct
14 Incorrect 119 ms 3164 KB Output isn't correct
15 Incorrect 38 ms 3164 KB Output isn't correct