글 읽기 - 반례를 모르겠습니다. 고수님들 부탁드려요

qktlf789456 3년 전 0

일단 풀어보자식으로 했고 시간초과가 나더라도 틀릴이유가 궁금하네요 .. 9%에서 틀렸습니다.

#include <iostream>
#include <algorithm>

#define EMPTY -1242152
using namespace std;


/*
6
2 1 2
2 3 3
1 2
1 2
2 1 -1
1 2
*/



int heap[10000000];
int heap_size = 0;

int q_size;



int tmp_link[10000];
int tmp_size = 0;


void insert_heap(int data)
{

	heap_size++;

	int current = heap_size - 1;
	int parent = (current - 1) / 2;

	while (current && data < heap[parent])
	{
		heap[current] = heap[parent];
		current = parent;
		parent = (current - 1) / 2;
	}

	heap[current] = data;

}


int delete_heap()
{
	if (heap_size == 0)
	{
		return EMPTY;
	}


	int return_value = heap[0];
	

	int data = heap[--heap_size];

	int current = 0;
	int child = 1;


	while (child < heap_size)
	{
		if (child + 1 < heap_size && heap[child] > heap[child + 1])
			child++;

		
		if (heap[child] >= data)
			break;

		heap[current] = heap[child];

		current = child;
		child = (current *2)+1;
	}


	heap[current] = data;

	return return_value;

}

void heapify()
{
	for (int i = 1; i < heap_size; i++)
	{


		int current = i;
		int data = heap[current];
		int parent = (current - 1) / 2;

		while (current && data > heap[parent])
		{
			heap[current] = heap[parent];
			current = parent;
			parent = (current - 1) / 2;
		}

		heap[current] = data;
	}
}


int main()
{
	cin >> q_size;
	
	int q,a,b;
	for (int _ = 0; _ < q_size; _++)
	{
		cin >> q;

		if (q == 1) //꺼내기
		{
			cin >> a;


			for (int i = 0; i < a - 1; i++)
			{
				tmp_link[tmp_size++] = delete_heap();
			}

			cout << delete_heap() << "\n";
			
			for (int i = 0; i < tmp_size; i++)
				insert_heap(tmp_link[i]);

			tmp_size = 0;

		}
		else //사탕넣기
		{
			cin >> a >> b; // a맛 사탕을 b개 넣는다

			if (b > 0) //양수일경우 넣고
			{
				for (int i = 0; i < b; i++)
					insert_heap(a);

			}
			else //음수일경우 뺀다.
			{
				b *= -1;
				int delete_count = b;
				for (int i = 0; i < heap_size; i++)
				{
					if (heap[i] == a)
					{
						b--;
						heap[i] = 99999999;
					}

					if (!b)
						break;

				}
				
					heapify();

					heap_size -= delete_count;
			}

		}

	}
	


	return 0;
}