글 읽기 - 도저희 틀린 이유를 못찾겠습니다.

alsidnf 4년 전 0

퀵소트로 강의 시작시간종료시간 따로 해서 정렬 후 +1은 강의시작 -1은 강의종료라고 하고 더하면 sum이 아직 안끝난 강의 수라고 생각하고 했습니다. 동시간때에 강의가 끝나서 자리가 났는데 강의실이 늘어나느 경우를 대비해 퀵소트에서 소트 우선순위를 -1이 1보다 위로오게 했습니다.

#include <cstdio>
int N,arr[400000][2];
int det(int a,int b)
{
    if(arr[a][0]<arr[b][0]) return 1;
    else if(arr[a][0]==arr[b][0] && arr[a][1]<arr[b][1]) return 1;
    return 0;
}
void swap(int a,int b)
{
    int temp;
    temp = arr[a][0]; arr[a][0]=arr[b][0]; arr[b][0]=temp;
    temp = arr[a][1]; arr[a][1]=arr[b][1]; arr[b][1]=temp;
}
void quick(int left,int right)
{
    int l,r,m;
    if(left<right)
    {
        l=left-1; r=right+1;
        m=(l+r)/2;
        while(1)
        {
            while(det(++l,m));
            while(det(m,--r));
            if(l>=r) break;
            swap(l,r);
        }
        quick(left,l-1);
        quick(r+1,right);
    }
}
int main()
{
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        scanf("%d%d",&arr[i][0],&arr[i+N][0]);
        arr[i][1]=1; arr[i+N][1]=-1;
    }
    quick(0,N*2-1);
    for(int i=0;i<N*2;i++) printf("%d %d\n",arr[i][0],arr[i][1]);
    int ans=1,sum=0;
    for(int i=0;i<N*2;i++)
    {
        sum+=arr[i][1];
        if(ans<sum) ans=sum;
    }
    printf("%d",ans);
}

nahwasa 4년 전 2

반례입니다.

3
999999999 1000000000
999999998 999999999 
1 999999998

답 : 1
출력 : 2

alsidnf 4년 전 1

감사합니다 ㅠㅠ 아이디어는 맞았는데 퀵소트를 잘못 했었네요 ㅠㅠㅠ

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

문제

문제

출처

ICPC

도저희 틀린 이유를 못찾겠습니다.

alsidnf 4년 전 0

nahwasa 4년 전 2

alsidnf 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말