글 읽기 - 시간 초과를 해결하려 했더니 출력 초과가 뜨네요

martinok1103 4년 전 0

원래 아래 코드에서 f함수 안의 incentidx와 postLeftEndIdx를 linear search로 찾았더니 시간초과가 나서 postpos와 inpos배열에 그 인덱스들을 저장해놨더니 출력 초과가 뜨네요

왜그럴까요???

#include<cstdio>

int n;
int post[100002];
int in[100002];

int postpos[100002];
int inpos[100002];

void f(int postst, int posten, int inst, int inen) {
    if(postst > posten) return;
    if(postst == posten) {
        printf("%d ",post[postst]);
        return;
    }

    int centval = post[posten];
    int incentidx = inpos[centval];
    printf("%d ", centval);

    int postLeftEndIdx = postpos[in[incentidx-1]];

    f(postst, postLeftEndIdx, inst, incentidx-1);
    f(postLeftEndIdx+1, posten-1, incentidx+1, inen);
}

int main()
{
    scanf("%d",&n);
    for(int i=1 ; i<=n ; i++) {
        scanf("%d",&in[i]);
        inpos[in[i]] = i;
    }
    for(int i=1 ; i<=n ; i++) {
        scanf("%d",&post[i]);
        postpos[post[i]] = i;
    }
    f(1, n, 1, n);
}

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

문제

문제

출처

ICPC

시간 초과를 해결하려 했더니 출력 초과가 뜨네요

martinok1103 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말