oj.uz

Submission #15739

# Submission time Handle Problem Language Result Execution time Memory
15739 2015-07-19T10:37:39 Z cki86201 버블 정렬 (OJUZ10_bubblesort) C++
0 / 100
 101 ms 2772 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[110];
	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 2772 KB Output isn't correct
2 Incorrect 0 ms 2772 KB Output isn't correct
3 Incorrect 0 ms 2772 KB Output isn't correct
4 Incorrect 0 ms 2772 KB Output isn't correct
5 Correct 0 ms 2772 KB Output is correct
6 Incorrect 0 ms 2772 KB Output isn't correct
7 Incorrect 0 ms 2772 KB Output isn't correct

Subtask #2
0.0 / 23.0

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

Subtask #3
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 2772 KB Output isn't correct
2 Incorrect 83 ms 2772 KB Output isn't correct
3 Incorrect 80 ms 2772 KB Output isn't correct
4 Incorrect 66 ms 2772 KB Output isn't correct
5 Incorrect 76 ms 2772 KB Output isn't correct
6 Incorrect 74 ms 2772 KB Output isn't correct
7 Incorrect 74 ms 2772 KB Output isn't correct
8 Incorrect 55 ms 2772 KB Output isn't correct
9 Incorrect 74 ms 2772 KB Output isn't correct
10 Incorrect 29 ms 2772 KB Output isn't correct
11 Incorrect 76 ms 2772 KB Output isn't correct
12 Incorrect 76 ms 2772 KB Output isn't correct
13 Incorrect 65 ms 2772 KB Output isn't correct
14 Incorrect 86 ms 2772 KB Output isn't correct
15 Incorrect 75 ms 2772 KB Output isn't correct

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 101 ms 2772 KB Output isn't correct
2 Incorrect 78 ms 2772 KB Output isn't correct
3 Incorrect 78 ms 2772 KB Output isn't correct
4 Incorrect 82 ms 2772 KB Output isn't correct
5 Incorrect 60 ms 2772 KB Output isn't correct
6 Incorrect 74 ms 2772 KB Output isn't correct
7 Incorrect 84 ms 2772 KB Output isn't correct
8 Incorrect 73 ms 2772 KB Output isn't correct
9 Incorrect 78 ms 2772 KB Output isn't correct
10 Incorrect 85 ms 2772 KB Output isn't correct
11 Incorrect 32 ms 2772 KB Output isn't correct
12 Incorrect 76 ms 2772 KB Output isn't correct
13 Incorrect 86 ms 2772 KB Output isn't correct
14 Incorrect 75 ms 2772 KB Output isn't correct
15 Incorrect 77 ms 2772 KB Output isn't correct