글 읽기 - 정렬 + 이분탐색 시간초과

heehcs 2년 전 0

출제자가 의도하는게 이 알고리즘이 아닌것같은데
힌트좀 주시면 감사하겠습니다.

#define loop(i,start,stop) for(int i = start; i < stop; i++)
#include <iostream>
#include <algorithm>
using  namespace std;
int a[1000005];
int T, N, M;
int x;

bool bs(int x) {
    int lo,hi;
    lo = -1;
    hi = N;

    while(lo + 1 < hi) {
        int mid = (lo+hi) / 2;
        if(a[mid] < x) {
            lo = mid;
        }
        else {
            hi = mid;
        }
    }
    return (a[hi] == x) ? true : false;
}


int main() {
    freopen("1.txt", "r", stdin);
    scanf("%d", &T);
    while(T--) {
        cin >> N;
        loop(i,0,N) {
            scanf("%d", &x);
            a[i] = x;
        }
        sort(a, a+N);

        cin >> M;
        while(M--) {
            cin >> x;
            if(bs(x)) {
                printf("1\n");
            }
            else {
                printf("0\n");
            }
        }
    }
}

poljjak 2년 전 1

cin이 scanf보다 속도가 느려서 시간초과가 나는 것으로 보입니다.

jh05013 2년 전 1

https://www.acmicpc.net/proble...

그리고 이걸 고치면 "틀렸습니다"를 받습니다.

heehcs 2년 전 0

결론은 제 binary search 함수의 문제로 판정이 되었는데요,

해답과 상관없이

위의 이분탐색 함수가 정확히 동작하지 않는 이유가 뭘까요?

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

문제

문제

출처

ICPC

정렬 + 이분탐색 시간초과

heehcs 2년 전 0

poljjak 2년 전 1

jh05013 2년 전 1

heehcs 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말