글 읽기 - 67퍼센트에서 시간초과가 납니다 ㅠㅠ 도와주세요

csp213 4년 전 0

count를 세는 부분이 시간이 많이 걸려서 시간초과가 나는 걸까요..? ㅠㅠㅠㅠ 혼자 해결할 수 없을 것 같아서 질문드립니다 ㅠㅠㅠ 도와주세요

#include<iostream>
#include<algorithm>

using namespace std;

int BinarySearch(int a[], int num, int n)
{
	int first = 0;
	int mid;
	int last = n - 1;
	int count = 1;
	while (first <= last)
	{
		mid = (first + last) / 2;
		if (num == a[mid])
		{
			if (mid != n - 1)
			{
				for (int i = mid; i < n - 1; i++)
				{
					if (a[i] == a[i + 1])
						count++;
					else
						break;
				}
			}

			if (mid != 0)
			{
				for (int i = mid; i > 0; i--)
				{
					if (a[i] == a[i - 1])
						count++;
					else
						break;
				}
			}
			return count;
		}
		else
		{
			if (num > a[mid])
				first = mid + 1;
			else
				last = mid - 1;
		}
	}
	return 0;
}

int s1[5000001] = { 0, };
int s2[5000001] = { 0, };

int main()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	int n1, n2;
	
	cin >> n1;

	for (int i = 0; i < n1; i++)
	{
		cin >> s1[i];
	}

	cin >> n2;
	
	for (int i = 0; i < n2; i++)
	{
		cin >> s2[i];
	}
	
	sort(s1, s1 + n1);

	for (int i = 0; i < n2; i++) 
	{
		cout << BinarySearch(s1, s2[i], n1) << " ";
	}
}

djm03178 4년 전 1

https://www.acmicpc.net/board/...

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

문제

문제

출처

ICPC

67퍼센트에서 시간초과가 납니다 ㅠㅠ 도와주세요

csp213 4년 전 0

djm03178 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말