글 읽기 - 어느 부분이 틀린건지 알 수 있을까요??

ldg1291 5년 전 0

이분탐색으로 풀었고 같은 경우가 여러번 있을 경우까지 고려하였습니다.

그런데 틀렸다고 나오네요..

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

vector<long long> arr[4];

vector<long long> sum1;
vector<long long> sum2;
set<int> poss;
long long res;

void find(long long t) {

	long long rpos = sum2.size() - 1;
	long long lpos = 0;

	while (lpos <= rpos) {

		int pos = (lpos + rpos) / 2;

		if (sum2[lpos] == -1 * t && poss.find(lpos)==poss.end()) {
			res++;
			poss.insert(lpos);
		}

		if (sum2[rpos] == -1 * t && poss.find(rpos) == poss.end()) {
			res++;
			poss.insert(rpos);
		}

		if (sum2[pos] == -1 * t && poss.find(pos) == poss.end()) {
			res++;
			poss.insert(pos);
		}

		if (sum2[pos] >= -1 * t) {
			rpos = pos - 1;
		} else 
			lpos = pos + 1;
	}
}

int main()
{
	int N;
	scanf("%d", &N);

	while (N--) {
		for (int i = 0; i < 4; i++) {
			long long num;
			scanf("%lld", &num);
			arr[i].push_back(num);
		}
	} 

	N = arr[0].size();

	for (long long i = 0; i < N; i++) {
		for (long long j = 0; j < N; j++) {
			sum1.push_back(arr[0][i] + arr[1][j]);
			sum2.push_back(arr[2][i] + arr[3][j]);
		}
	}

	sort(sum2.begin(), sum2.end());

	for (long long i = 0; i < sum1.size(); i++) {
		find(sum1[i]);
	}

	cout << res << endl;
}

djm03178 5년 전 1

이분 탐색을 하는데 과연 lpos, rpos, pos 3개만 검사해서 같은 수가 여러 번 있는 경우를 전부 셀 수 있을까요?

이 문제는 lower bound와 upper bound를 사용해서 풀어야 합니다.

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

문제

문제

출처

ICPC

어느 부분이 틀린건지 알 수 있을까요??

ldg1291 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말