글 읽기 - 어퍼바운드를 직접 구현했는데 어느 부분에서 틀렸을까요?? ㅠㅠ

skyde47 4년 전 0

우선 모든 Input이 0일때, N=2, N=4,N=10 의 값은 잘 나왔습니다.

이분탐색 할때 pivot이 같을때도 오른쪽으로 옮겨서 같은 값들 중 맨 오른쪽으로 커서를 옮긴다는 생각으로 소스를 구현했는데 어디서 문제가 생겼을까요? ㅠㅠ

#include<stdio.h>
int n, a[4000], b[4000], c[4000], d[4000], ab[16000000], cd[16000000], sort[16000000],tmp;
long long int ret;

void mergesort(int l, int r,int *arr) {
	if (l >= r)return;
	int mid = (l + r + 1) / 2;
	int ll = l, rr = mid, cnt = l;
	while (ll<mid&&rr<=r) {
		if (arr[ll] > arr[rr])sort[cnt++] = arr[rr++];
		else sort[cnt++] = arr[ll++];
	}
	while (ll < mid)sort[cnt++] = arr[ll++];
	while (rr <= r)sort[cnt++] = arr[rr++];
	for (int i = l; i < cnt; i++)arr[i] = sort[i];
}

void merge(int l, int r,int *arr) {
	if (l >= r)return;
	int mid = (l + r + 1) / 2;
	merge(l, mid - 1,arr);
	merge(mid, r,arr);
	mergesort(l, r,arr);
}

int main() {
	scanf("%d", &n);
	for (int j = 0; j < n; j++)scanf("%d %d %d %d", &a[j], &b[j], &c[j], &d[j]);
	for (int i = 0; i < n; i++)for (int j = 0; j < n; j++) {
		ab[i*n + j] = a[i] + b[j];
		cd[i*n + j] = c[i] + d[j];
	}
	merge(0, n*n - 1, ab);
	merge(0, n*n - 1, cd);
	for (int i = 0; i < n*n; i++) {
		if (i>0&&ab[i] == ab[i - 1]) {
			ret += tmp;
			continue;
		}
		int l = 0, r = n * n - 1, comp = ab[i] * -1;
		while (l <= r) {
			int mid = (l + r) / 2;
			if (cd[mid] <= comp)l = mid + 1;
			else r = mid - 1;
		}
		if (cd[r] == comp) {
			tmp++;
			for (int j = r; j >0 && cd[j] == cd[j - 1]; j--)tmp++;
			ret += tmp;
		}
		else tmp = 0;
	}
	printf("%lld", ret);
}

skyde47 4년 전 0

47번줄에 tmp 초기화 관련 문제였습니다 ㅠㅠ

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

문제

문제

출처

ICPC

어퍼바운드를 직접 구현했는데 어느 부분에서 틀렸을까요?? ㅠㅠ

skyde47 4년 전 0

skyde47 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말