글 읽기 - 어디가 틀렸을까요ㅠㅠㅠㅠ

cho31250 8년 전 0

binary search로 풀었는데

시간초과가 뜨는데ㅠ 어떻게 해결해야할까요ㅠ

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <functional>
using namespace std;

int a[500002];
int b[500002][2];
int cnt[500002];
int seq[500002];
int n, m;

void b_search(int idx,int left, int right){

	while (left <= right){
		int mid = (left + right) / 2;
		if (b[idx][0] < a[mid]) right = mid - 1;
		else if (a[mid] < b[idx][0]) left = mid + 1;
		else {
			b[idx][1]++;

			for (int i = mid + 1; i < n; i++){
				if (a[i] == b[idx][0]){
					b[idx][1]++;
				}
				else{
					break;
				}
			}

			for (int i = mid - 1; i >= 0; i--){
				if (a[i] == b[idx][0]){
					b[idx][1]++;
				}
				else{
					break;
				}
			}
			\
				return;
		}
	}

	
}


int b_search2(int idx, int left, int right){

	while (left <= right){
		int mid = (left + right) / 2;
		if (idx > seq[mid]) right = mid - 1;
		else if (idx < seq[mid]) left = mid + 1;
		else return seq[mid];
	}
	return -1;
}

int main()
{
	
	scanf("%d", &n);
	for (int i = 0; i < n; i++){
		scanf("%d", &a[i]);
	}

	scanf("%d", &m);
	int t = 0;
	for (int i = 0; i < m; i++){
		int temp;
		scanf("%d", &temp);

		if (b_search2(temp, 0, t-1) == -1){
			seq[t] = temp;
			if (t != 0){
				sort(seq, seq + t - 1);
			}
			b[t++][0] = temp;
		}
	}

	sort(a, a + n);

	for (int i = 0; i < t; i++){
		b_search(i,0,n-1);
		printf("%d ", b[i][1]);
	}
	printf("\n");

}

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

문제

문제

출처

ICPC

어디가 틀렸을까요ㅠㅠㅠㅠ

cho31250 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말