글 읽기 - 반례가 궁금합니당

av3rs1on 2년 전 0

예제코드 및 돌아다니는 반례들 인터넷까지 다 해봤는데 전부 통과됩니다..

반례가 무엇인지와 어느곳에서 틀린지 궁금합니다!

#include <iostream>
#include <queue>
using namespace std;

class Info {
public:
	int a;
	int b;
};

struct compare {
public:
	bool operator()(const Info& in1, const Info& in2) {
		return in1.b > in2.b;
	}
};

int main(void) {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	priority_queue<Info, vector<Info>, compare> pq;

	int n = 0, m = 0;
	cin >> n;
	Info info;
	for (int i = 0; i < n; i++) {
		cin >> m;
		info.a = m;
		info.b = abs(m);
		if (m != 0) {
			pq.push(info);
		}
		else  if (m == 0 && pq.empty()) {
			cout << 0 << '\n';
		}
		else if (m == 0 && pq.size() > 1) {
			auto a = pq.top().a;
			pq.pop();
			if (abs(a) == abs(pq.top().a)) {
				auto b = pq.top().a;
				pq.pop();
				if (a > b) {
					info.a = a;
					info.b = abs(a);
					pq.push(info);
					cout << b << '\n';
				}
				else {
					info.a = b;
					info.b = abs(b);
					pq.push(info);
					cout << a << '\n';
				}
			}
			else {
				cout << a << '\n';
			}
		}
		else {
			cout << pq.top().a << '\n';
			pq.pop();
		}
	}

	return 0;
}

yijw0930 2년 전 0

중복된 숫자가 입력될 경우 절댓값이 같은 수가 동시에 세 개 이상 존재할 수 있습니다.

이 경우의 반례는 다음과 같습니다.

av3rs1on 2년 전 0

아하.. 그 생각을 못했네요 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례가 궁금합니당

av3rs1on 2년 전 0

yijw0930 2년 전 0

av3rs1on 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말