글 읽기 - 테스트 케이스는 통과하는데 제출하면 바로 틀리네요

spparty 1년 전 0

lower_bound로 접근했는데 틀린 부분이 있을까요??

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int arr[100001] = {0, };
int N, M;
vector<int> answer;

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

    cin >> N;
    for (int i=0; i<N; i++)
    {
        int num;
        cin >> num;
        arr[i] = num;
    }    

    sort(arr, arr + 100001);

    cin >> M;
    for (int i=0; i<M; i++)
    {
        int num;
        cin >> num;
        if (lower_bound(arr, arr+100001, num)!= arr+100001)
            answer.push_back(1);
        else
            answer.push_back(0);
    }

    for (auto n : answer)
        cout << n << endl;
}

kwakws0627 1년 전 1

sort 하고 lower_bound 를 할 때 범위를 배열 전체(0 ~ 100'001) 까지 히자 말고 입력받는 숫자 크기만큼만 해야 합니다.

arr 배열이 전역 범위에 선언되어 있어서 초기값이 전부 0으로 초기화 되면서

아래와 같은 반례가 생깁니다.

// input
5
1 2 3 4 5
1
0

// wrong output
1

// ans
0

spparty 1년 전 0

고치긴 했는데 시간초과 뜨네요 ㅋㅋ.. 다른 방식으로 접근해야 할 듯 하네요

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

문제

문제

출처

ICPC

테스트 케이스는 통과하는데 제출하면 바로 틀리네요

spparty 1년 전 0

kwakws0627 1년 전 1

spparty 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말