글 읽기 - 반례를 못 찾겠습니다..

kmes055 4년 전 0

Stack을 이용해 풀었는데 아무리 생각해도 어떤 예외가 남았는지 모르겠네요..

Input: 10 1 7 3 15 5 11 7 9 8 5 9 6 10 12 12 13 14 10 16 9 10 4 15 6 10 2 5 12 13 12 17 10 15 7 9 3 10 8 9 8 10

Output: maybe maybe false maybe maybe false true maybe false false

위 TC도 잘 통과하고 원본 Test case도 잘 통과하는데 어디가 문제인지 모르겠습니다.

#define fi(a) for(int i = 0; i < a; i++)
#define num 50000

#include <cstdio>
#include <cassert>

int y[num];
int r[num];
int st[num];
int p[num] = { -1 };
int n, m, a, b, t = -1;

int bsearch(int l, int r, int k) {
	if (l < r) {
		int mid = (l + r) / 2;
		if (y[mid] == k) return mid;
		if (y[mid] < k) return bsearch(mid + 1, r, k);
		else return bsearch(l, mid, k);
	}
	else return l;
}

int main() {

	scanf("%d", &n);
	fi(n) {
		scanf("%d %d", y + i, r + i);
		while (t > -1 && r[i] > r[st[t]]) t--;	
		p[i] = t == -1 ? -1 : st[t], st[++t] = i;
	}
	scanf("%d", &m);
	fi(m) {
		scanf("%d %d", &a, &b);
		int ai = bsearch(0, n - 1, a), bi = bsearch(0, n - 1, b);
		
		if (a != y[ai] && b != y[bi]) printf("maybe\n");
		else if (a != y[ai]) {
			if (p[bi] < ai) printf("maybe\n");
			else printf("false\n");
		}
		else if (b != y[bi]) {
			if (b < y[n - 1] && bi == ai + 1) printf("maybe\n");
			else {
				int it = b > y[n - 1] ? n - 1 : bi - 1;
				while (p[it] != -1 && p[it] > ai) it = p[it];
				if (p[it] == ai && r[it] < r[ai]) printf("maybe\n");
				else printf("false\n");
			}
		}
		else if (p[bi] == ai) {
			if (b - a == bi - ai) printf("true\n");
			else printf("maybe\n");
		}
		else printf("false\n");
	}
	return 0;
}

yukino 4년 전 0

혹시 이거 해보셨나요?

input:
1
1 1
2
1 2
1 3

output:
maybe
maybe

parkpkww 4년 전 0

위에 반례로

input:

1 1

1 2

1 3

output:

maybe

를 들어주셨는데요....

"Y < Z < X를 만족하는 모든 Z들에 대해서, Z년도의 강수량은 X년도보다 적다." 라는 조건이 있기 때문에 위 반례의 두번째 output 은 false가 되어야 하지 않나요...?

1 2 3 년도를 본다고 생각하고 1년도 강수량이 1 이라고 주어졌으면 3년도 강수량은 1 일 수 밖에 없고 이때 강수량은 r(1 ≤ r ≤ 1,000,000,000) 로 주어졌으므로 2년도에 맞는 강수량을 가정할 수 없을 것 같아요!

yukino 4년 전 0

@parkpkww

맞네요;;

1년 강수량 1이 아니라 더 큰 수를 줘야 됬네요

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

문제

문제

출처

ICPC

반례를 못 찾겠습니다..

kmes055 4년 전 0

yukino 4년 전 0

parkpkww 4년 전 0

yukino 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말