글 읽기 - 런타임 에러가 뜨는 입력을 아무 거나 하나만 찾아주세요

portableangel 5년 전 0

틀리거나 시간초과라면 이해하고 디버깅하겠지만, 런타임 에러는 도무지 이해할 수가 없습니다.

런타임에러만 아닌 결과를 받으면 퇴근하려고 했는데, 지금 이러다 버스 끊기겠습니다.

아무 입력이나 좋으니, 런타임에러가 뜨는 입력을 하나만 찾아주실 수 있을까요?

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <functional>
#include <utility>

using namespace std;

typedef long long lli;
typedef pair<int, int> ip;

class p {
public:
	lli x, h;
};

bool cmp(const p &i, const p &j) {
	return i.x < j.x;
}

int d[1 << 22], n, sz = 1;
int bt[1 << 22];
p list[1000001];

void lmaketree(int l, int r) {
	if (l + 1 == r) return;
	for (int i = l; i < r; i += 2)
		bt[i / 2] = min(bt[i], bt[i + 1]);
	lmaketree(l / 2, r / 2);
}

void lupd(int k, int s) {
	if (k == 0) return;
	bt[k] = min(bt[k], s);
	lupd(k / 2, s);
}

int lf(int l, int r, int s) {
	if (l >= r) return l == r ? min(s, bt[l]) : s;
	if (l % 2 == 0 && r % 2) return lf(l / 2, r / 2, s);
	else if (l % 2 == 0 && r % 0 == 0) return lf(l / 2, r / 2 - 1, min(s, bt[r]));
	else if (l % 2 && r % 2) return lf(l / 2 + 1, r / 2, min(s, bt[l]));
	else return lf(l / 2 + 1, r / 2 - 1, min(s, min(bt[l], bt[r])));
}

void maketree(int l, int r) {
	if (l + 1 == r) return;
	for (int i = l; i < r; i += 2)
		d[i / 2] = min(d[i], d[i + 1]);
	maketree(l / 2, r / 2);
}

int f(int l, int r, int s) {
	if (l >= r) return l == r ? min(s, d[l]) : s;
	if (l % 2 == 0 && r % 2) return f(l / 2, r / 2, s);
	else if (l % 2 == 0 && r % 0 == 0) return f(l / 2, r / 2 - 1, min(s, d[r]));
	else if (l % 2 && r % 2) return f(l / 2 + 1, r / 2, min(s, d[l]));
	else return f(l / 2 + 1, r / 2 - 1, min(s, min(d[l], d[r])));
}

void upd(int k, int s) {
	if (k == 0) return;
	d[k] = min(d[k], s);
	upd(k / 2, s);
}

priority_queue<ip, vector<ip>, greater<ip> > q;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%lld %lld", &list[i].x, &list[i].h);
	sort(list + 1, list + n + 1, cmp);
	while (sz < n + 1) sz *= 2;
	bt[sz + 1] = 1;
	for (int i = 2; i < sz * 2; i++)
		bt[sz + i] = (1 << 30);
	lmaketree(sz, sz * 2);
	for (int i = 2; i <= n; i++) {
		int pos = i;
		if (list[i].h >= list[i].x - list[1].x)	pos = 1;
		else if (list[i].h < list[i].x - list[i - 1].x) pos = i;
		else {
			int lo = 1, hi = i - 1;
			while (lo + 1 < hi) {
				int mid = (lo + hi) / 2;
				if (list[i].x - list[mid].x <= list[i].h) hi = mid;
				else lo = mid;
			}
			pos = min(pos, lf(sz + hi, sz + i - 1, (1 << 30)));
		}
		lupd(sz + i, pos);
	}
	d[sz + 1] = 1;
	for (int i = sz + 2; i < sz * 2; i++)
		d[i] = (1 << 30);
	maketree(sz, sz * 2);
	q.push(ip(0, 1));
	for (int i = 2; i <= n; i++) {
		if (bt[sz + i] > n) while (1);
		int lpos = bt[sz + i], res = f(sz + lpos - 1, sz + i - 1, (1 << 30)) + 1;
		while (!q.empty()) {
			lli x1 = list[q.top().second].x, h1 = list[q.top().second].h;
			if (x1 + h1 < list[i].x) q.pop();
			else break;
		}
		if (!q.empty()) res = min(res, q.top().first + 1);
		q.push(ip(d[sz + i - 1], i));
		upd(sz + i, res);
	}
	printf("%d\n", d[sz + n]);
	return 0;
}

portableangel 5년 전 7

찾았습니다. 집에 가야지..

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

문제

문제

출처

ICPC

런타임 에러가 뜨는 입력을 아무 거나 하나만 찾아주세요

portableangel 5년 전 0

portableangel 5년 전 7

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말