글 읽기 - 고수님들! 계산 해보면, 시간초과 아닌 것 같은데, 시간초과라고 나옵니다.

overpower 7년 전 1

<x:y> 를 찾을 때

x + m * i == y + n * j (i 와 j는 서로 다른 정수)

를 만족하는 i, j 가 i <= n , j <= m 안에 있으면 그 때의 x + m * i 값이 해당년도가 되므로,

그 값을 출력하고, 범위를 넘어서면 -1 을 출력하도록 하였습니다. (년도 maximum이 n과m의 최소공배수이기 때문에)

i를 for로 n 번 돌고

그 각각의 i에 대하여, 위의 조건을 만족하는 j를 바이너리 서치로 log m 안에 찾으면,

n * log m 안에 찾아지는 거 아닌가요? (0 < n,m < 40000)

예제는 잘 돌아가고, 제가 임의로 큰 수를 집어 넣어도 잘 돌아가는데, 채점결과는 시간초과가 나오네요;; (설마, 테스트 케이스가 엄청 많은건가;;)

고수님들, 알려주세요!!!

#include <cstdio>

bool bs(int target,int start,int end,int term)
{
    if(start > end) return false;

    int half = ((end-start)/term)/2;
    if(target == start + term*half) return true;
    else if(target < start + term*half) return bs(target,start,start+term*(half-1),term);
    else return bs(target,start+term*(half+1),end,term);
}

int sol(int m,int n,int x,int y)
{
    for(int i=0;i<=n;i++)
        if(bs(x+m*i,y,y+n*m,n)) return x+m*i;
    return -1;
}

int main()
{
    int t;
    scanf("%d",&t);
    for(int i=0;i<t;i++)
    {
        int m,n,x,y;
        scanf("%d %d %d %d",&m,&n,&x,&y);
        printf("%d\n",sol(m,n,x,y));
    }
    return 0;
}

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

문제

문제

출처

ICPC

고수님들! 계산 해보면, 시간초과 아닌 것 같은데, 시간초과라고 나옵니다.

overpower 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말