글 읽기 - c++ 시간초과

ljm31415 3년 전 0

시간초과가 왜 나는건가요?

정렬은 퀵 정렬 썼어요

#include<cstdio>
#include<algorithm>

using namespace std;

int n, a[4000], b[4000], c[4000], d[4000], ab[16000000], cd[16000000], cnt=0;

int partition(int arr[], int left, int right)
{
    int pivot, temp;
    int low, high;

    low = left;
    high = right + 1;
    pivot = arr[left];
    do
    {
        do
        {
            low++;
        }while(low<=right && arr[low]<pivot);

        do
        {
            high--;
        }while (high>=left && arr[high]>pivot);

        if(low<high)
            swap(arr[low], arr[high]);
    }while(low<high);

    swap(arr[left], arr[high]);

  return high;
}

void quick_sort(int arr[], int left, int right)
{
    if(left<right)
    {
        int q = partition(arr, left, right);

        quick_sort(arr, left, q-1);
        quick_sort(arr, q+1, right);
    }

}

int main()
{
    scanf("%d", &n);
    for(int i=0; i<n; i++)
        scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]);

    quick_sort(a, 0, n-1);
    quick_sort(b, 0, n-1);
    quick_sort(c, 0, n-1);
    quick_sort(d, 0, n-1);

    for(int i=0; i<n*n; i++)
    {
        ab[i]=a[i/n]+b[i%n];
        cd[i]=c[i/n]+d[i%n];
    }

    quick_sort(ab, 0, n*n-1);
    quick_sort(cd, 0, n*n-1);

    for(int i=0; i<n*n; i++)
    {
        for(int j=n*n-1; j>=0; j--)
        {
            if(ab[i]+cd[j]==0)
                cnt++;
        }
    }
    printf("%d", cnt);
}

line_jin 3년 전 0

69 ~ 76번의 코드가 돌아가는량이 약 4000⁴ 번 돌아가는 것으로 보입니다.

1초기준 약 1~2억정도의 시간복잡도가 적절하므로 이부분에서 시간을 줄여보시는 것을 추천드립니다.

ljm31415 3년 전 0

이렇게 수정해봤는데 50% 부근에서 시간초과가 나네요...

어떻게 고쳐야 할까요?

for(int i=0; i<n*n; i++)
    {
        int left=0, right=n*n-1;
        while(left+1<right)
        {
            int mid=(left+right)/2;
            int x=ab[i]+cd[mid];
            if(x==0)
            {
                cnt++;
                int one=0, two=0;
                for(int j=1; j<right-mid; j++)
                {
                    if(cd[mid+j]!=cd[mid])
                        one=1;
                    if(cd[mid-j]!=cd[mid])
                        two=1;
                    if(one==1 && two==1)
                        break;
                    if(one==0)
                        cnt++;
                    if(two==0)
                        cnt++;
                }
                break;
            }
            else if(x>0)
                right=mid;
            else
                left=mid;
        }
    }

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

문제

문제

출처

ICPC

c++ 시간초과

ljm31415 3년 전 0

line_jin 3년 전 0

ljm31415 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말