글 읽기 - 78% segfault 발생

dongu4 3년 전 0

78%에서 segfault 발생합니다. 스크립트로 n=1000에 대한 랜덤한 케이스로 실행해도 문제없이 실행됩니다.

질문 게시판의 반례들 모두 잘 됩니다.

살려주세요.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <list>
#include <stack>
using namespace std;

int main()
{
    int n;
    scanf("%d", &n);

    int arr[1004];
    pair<int, int> p[1004];


    int i,j;
    for(i=0;i<n;i++) scanf("%d", &arr[i]);
    for(i=0;i<1004;i++) p[i] = make_pair(1, 0);


    for(i=0;i<n;i++)
    {
        int x, y;
        x = -1; y = -1;
        for(j=0;j<i;j++)
        {
            if(arr[i] > arr[j])
            {
                if(x < p[j].first)
                {
                    x = p[j].first;
                    y = j;
                }
            }
        }
        if(x == -1)
        {
            p[i] = make_pair(1, arr[i]);
        }
        else
        {
            p[i] = make_pair(x+1, y);
        }
    }
    
    stack<int> s;
    int m;
    
    int xx = p[0].first;
    for(i=0;i<n;i++)
    {
        if(p[i].first > xx)
        {
            m = i;
            xx = p[i].first;
        }
    }

    int t;
    s.push(m);
    while(1)
    {
        if(p[m].first == 1) break;
        s.push(p[m].second);
        m = p[m].second;
    }

    printf("%d\n", xx);
    while(!s.empty())
    {
        printf("%d ", arr[s.top()]);
        s.pop();
    }
    printf("\n");

}

dldyddlwl 3년 전 1

[반례]

일 때,

m은 초기화되지 못한채로 s.push(m)을 거친 후에, p[m]으로, 인덱스로 사용됩니다. 충분히 런타임에러가 발생할 수 있습니다.

 int m;
    
    int xx = p[0].first;
    for(i=0;i<n;i++)
    {
        if(p[i].first > xx)
        {
            m = i;
            xx = p[i].first;
        }
    }

    int t;
    s.push(m);
    while(1)
    {
        if(p[m].first == 1) break;
        s.push(p[m].second);
        m = p[m].second;
    }

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

문제

문제

출처

ICPC

78% segfault 발생

dongu4 3년 전 0

dldyddlwl 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말