제출 #13962

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
13962		gs14004	버블 정렬 (OJUZ10_bubblesort)	C++14	0 / 100	69 ms	4020 KiB

bubblesort

#include <cstdio>
#include <queue>
#include <set>
using namespace std;
typedef pair<int,int> pi;

int n,k,a[100005],ret[100005];
bool vis[100005];
int sorted_pos[100005];
priority_queue<pi> pq;

int main(){
    scanf("%d %d",&n,&k);
    for (int i=0; i<n; i++) {
        scanf("%d",&a[i]);
        pq.push(pi(a[i],i));
    }
    int pt = n;
    while (!pq.empty()) {
        pi t = pq.top();
        pq.pop();
        sorted_pos[t.second] = --pt;
        if(pt >= n-k) vis[t.second] = 1,ret[pt] = t.first;
    }
    for (int i=0; i<n; i++) {
        if(!vis[i] && i - sorted_pos[i] >= k){
            ret[i - k] = a[i];
            vis[i] = 1;
        }
    }
    int p = 0;
    for (int i=0; i<n; i++) {
        while (ret[p]) {
            p++;
        }
        if(!vis[i]) ret[p++] = a[i];
    }
    for (int i=0; i<n; i++) {
        printf("%d ",ret[i]);
    }
}

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