글 읽기 - 뭐가 문제일까요?

rolypolyvg295 7년 전 0

처음 부터 틀린는데
뭐가 문제일까요?
#include <stdio.h>
#include <stdlib.h>

#define first(n) (((n)-1)/2)
#define second(n) ((n) - ((n)-1)/2-1)

typedef struct _DATA{
	unsigned short data;
	int index, which;
} DATA;

typedef struct _TREE{
	int n;
	DATA **ele;
} TREE;

typedef struct MTREE{
	TREE *high_low[2];
	DATA *median;
} MTREE;

enum {NONE = -2, MEDIAN, HIGH, LOW};

void treeSort(TREE *tr, DATA *dat, int n, int type);
int peekM(MTREE *mt, int where);
DATA *popM(MTREE *mt, int index, int type);
DATA *pop(TREE *tr, int index, int type, void (*func)(TREE*,int,int));
void pushM(MTREE *mt, DATA *da, int where);
void push(TREE *tr, DATA *da, int type, void (*func)(TREE*,int,int));
TREE *intialize(int n);
void freeTree(TREE *tr);
MTREE *intializeM(int n);
void freeMtree(MTREE *mt);
int compareByData(DATA *a, DATA *b);
void swapNor(TREE *tr, int a, int b);
void swap(TREE *tree, int a, int b);
void swapInt(int *a, int *b);

int main(void)
{
    int n, k;
    int i, j;
    DATA *dat, *tmp;
    TREE *sort;
    MTREE *ans;
    long long int sum = 0;

    scanf("%d %d", &n, &k);

    dat = malloc(k * sizeof(DATA));
    sort = intialize(k);

    for (i = 0; i < k; ++i)
        scanf("%hu", &(dat[i].data));

    treeSort(sort, dat, k, HIGH);

    for (i = 0; i < first(k); ++i)
        sort->ele[i]->which = HIGH;

    sort->ele[i++]->which = MEDIAN;

    for (;i < k; ++i)
        sort->ele[i]->which = LOW;

    freeTree(sort);

    ans = intializeM(k);

    for (i = 0; i < k; ++i)
        pushM(ans, dat+i, dat[i].which);

    sum += ans->median->data;

    for (j = 0; i < n; ++i){
        popM(ans, dat[j].index, dat[j].which);
        scanf("%hu", &(dat[j].data));
        pushM(ans, dat+j, dat[j].which);
        if (peekM(ans, HIGH) > peekM(ans, MEDIAN)){
            tmp = popM(ans, 0, HIGH);
            pushM(ans, ans->median, HIGH);
            pushM(ans, tmp, MEDIAN);
        }

        if (peekM(ans, MEDIAN) > peekM(ans, LOW)){
            tmp = popM(ans, 0, LOW);
            pushM(ans, ans->median, LOW);
            pushM(ans, tmp, MEDIAN);
        }

        if (peekM(ans, HIGH) > peekM(ans, MEDIAN)){
            tmp = popM(ans, 0, HIGH);
            pushM(ans, ans->median, HIGH);
            pushM(ans, tmp, MEDIAN);
        }

        sum += ans->median->data;

        if (++j == k)
            j = 0;
    }

    freeMtree(ans);
    free(dat);

    printf("%lld\n", sum);

	return 0;
}

void treeSort(TREE *tr, DATA *dat, int n, int type)
{
    int i;

    for (i = 0; i < n; ++i)
        push(tr, dat+i, type, &swapNor);

    for (i = 0; i < n; ++i)
        pop(tr, 0, type, &swapNor);

    return;
}

int peekM(MTREE *mt, int where)
{
    if (where == MEDIAN)
        return (int) mt->median->data;

    if (mt->high_low[where]->n == 0)
        return where*70000-1;
    return (int) mt->high_low[where]->ele[0]->data;
}

void pushM(MTREE *mt, DATA *da, int where)  // where = -1 median, where = 0 high  where = 1 low
{
    da->which = where;
    if (where == MEDIAN){
        da->index = 0;
        mt -> median = da;
    }else{
        da->index = mt->high_low[where]->n;
        push(mt->high_low[where], da, where, &swap);
    }

    return;
}

void push(TREE *tr, DATA *da, int type, void (*func)(TREE*,int,int))
{
    int mover, up;

    tr->ele[tr->n] = da;

    for (mover = tr->n; mover; mover = up){
        up = (mover-1)/2;
        if (compareByData(tr->ele[up], tr->ele[mover]) == type)
            break;
        else
            func(tr, mover, up);
    }

    tr->n++;

    return;
}

DATA *popM(MTREE *mt, int index, int type)
{
    DATA *ret;

    if (type == MEDIAN){
        ret = mt->median;
        mt->median = NULL;
    }else
        ret = pop(mt->high_low[type], index, type, &swap);

    return ret;
}

DATA *pop(TREE *tr, int index, int type, void (*func)(TREE*,int,int))
{
    int mover, i, change, down, current;
    DATA *ret;

    tr->n--;
    func(tr, index, tr->n);
    ret = tr->ele[tr->n];

    current = index;
    do{
        mover = change = current;
        for (i = 1; i <= 2; ++i){
            down = 2 * mover + i;
            if (down < tr->n && (compareByData(tr->ele[down], tr->ele[change]) == type))
                change = down;
        }
       func(tr, change, mover);
       current = change;
    } while(change != mover);

    return ret;
}

int compareByData(DATA *a, DATA *b)
{
    return a->data < b->data;
}

void swapNor(TREE *tr, int a, int b)
{
    DATA *tmp;

    if (a == b)
        return;

    tmp = tr->ele[a];
    tr->ele[a] = tr->ele[b];
    tr->ele[b] = tmp;

    return;
}

void swap(TREE *tree, int a, int b)
{
	DATA *tmp;

	if (a == b)
        return;

	swapNor(tree, a, b);

	swapInt(&tree->ele[a]->index, &tree->ele[b]->index);
	swapInt(&tree->ele[a]->which, &tree->ele[b]->which);

	return;
}

void swapInt(int *a, int *b)
{
	int tmp;

	tmp = *a;
	*a = *b;
	*b = tmp;
	return;
}

void freeTree(TREE *tr)
{
    free(tr->ele);
    free(tr);
    return;
}

void freeMtree(MTREE *mt)
{
    int i;
    for (i = 0; i < 1; ++i)
        freeTree(mt->high_low[i]);
    free(mt);
}

TREE *intialize(int n)
{
    TREE *tr;
    tr = malloc(sizeof(TREE));
	tr -> ele = malloc(n * sizeof(DATA*));
	tr -> n = 0;

	return tr;
}

MTREE *intializeM(int n)
{
	int i;

	MTREE *mt;
	mt = malloc(sizeof(MTREE));
	mt->high_low[HIGH] = intialize(first(n));
	mt->high_low[LOW] = intialize(second(n));


	return mt;
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

뭐가 문제일까요?

rolypolyvg295 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
