Submission #13981

#	Time	Username	Problem	Language	Result	Execution time	Memory
13981		kriii	버블 정렬 (OJUZ10_bubblesort)	C++14	100 / 100	84 ms	4424 KiB

bubblesort

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

int N,K;
struct pos{
	int x,i;
	bool operator <(const pos t) const{
		if (x == t.x) return i < t.i;
		return x < t.x;
	}
}P[100005];

const int Z = 1<<17;

int it[2][Z*2],A[Z];

int sum(int *it, int y)
{
	int s = 0;
	int x = Z; y += Z;
	while (x < y){
		if (x & 1) s += it[x++];
		if (~y & 1) s += it[y--];
		x /= 2; y /= 2;
	} if (x == y) s += it[x];
	return s;
}

int trace(int *it, int x)
{
	int s = 1;
	while (s < Z){
		s *= 2;
		if (it[s] <= x){
			x -= it[s];
			s++;
		}
	}
	return s - Z;
}

void del(int *it, int x)
{
	x += Z;
	while (x){
		it[x]--;
		x /= 2;
	}
}

int main()
{
	scanf ("%d %d",&N,&K);
	for (int i=0;i<N;i++){
		scanf ("%d",&P[i].x);
		P[i].i = i;
	}
	sort(P,P+N);

	for (int k=0;k<2;k++){
		for (int i=0;i<N;i++) it[k][i+Z] = 1;
		for (int j=Z-1;j>=1;j--) it[k][j] = it[k][j*2] + it[k][j*2+1];
	}

	for (int i=0;i<N;i++){
		int u = max(0,sum(it[0],P[i].i)-K-1);
		int x = trace(it[1],u);
		A[x] = P[i].x;
		del(it[0],P[i].i);
		del(it[1],x);
	}

	for (int i=0;i<N;i++){
		printf ("%d ",A[i]);
	}
	return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 47 / 47
• Subtask 4: 19 / 19