Submission #15815

#	Time	Username	Problem	Language	Result	Execution time	Memory
15815		jihoon	버블 정렬 (OJUZ10_bubblesort)	C++98	34 / 100	1000 ms	65536 KiB

bubblesort

#include<cstdio>
#include<deque>
#include<vector>
using namespace std;

int n,k;
vector< deque<int> > tree;
int su[100001];
int sons[100001];
int head;

void bubble(int parent){
	int i;
	for(i=0;i<sons[parent];i++){
		bubble(tree[parent][i]);		
	}
	if(sons[parent]<2) return;
	head=tree[parent][0];
	for(i=1;i<sons[parent];i++){
		if(su[head]>su[tree[parent][i]]){
			tree[head].push_back(tree[parent][i]);
		}else{
			tree[tree[parent][i]].push_front(head);
			head=tree[parent][i];
		}
		sons[head]++;
	}
	tree[parent].clear();
	tree[parent].push_back(head);
	sons[parent]=1;
}

void aprint(int parent){
	int i;
	for(i=0;i<sons[parent];i++){
		aprint(tree[parent][i]);
	}
	if(parent>0) printf("%d ",su[parent]);
}

int main(){
	int i;
	scanf("%d %d",&n,&k);
	tree.resize(n+1);
	for(i=1;i<=n;i++){
		scanf("%d",&su[i]);
		tree[0].resize(n);
		tree[0][i-1]=i;
	}
	sons[0]=n;
	for(i=0;i<k;i++) bubble(0);
	aprint(0);
}

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