글 읽기 - 헐.. std::sort 내부 과정이 어떻게 되나요?

portableangel 9년 전 0

요거 값 다 2147483648을 더해서 0 이상의 수로 바꿔주고 radix sort로 풀면 std::sort보다 빠를거 같아서 해봤는데

std::sort는 800MS, radix sort는 시간초과가 떠서요

0 이상의 수로 만들어주는 과정에 쓴 덧셈 연산이 느리거나, 큐 푸시/팝 연산이 느리거나

아니면 구현 자체가 멍청했을 가능성도 있지만 ㅠㅠ

std::sort가 어떤 원리로 동작하길래 이렇게까지 빠른지 궁금해서요

movie_jo 9년 전 2

2분 32초부터 보시면...

pichulia 9년 전 2

long long 으로 연산하는건 생각보다 시간이 오래걸리는 일입니다.

그래서 unsigned int로 계산하면 적당히 빨라지지 않을까 하는 생각에서 radix sort를 짜봤는데..역시나 TLE더라고요ㅋㅋㅋ

그래서 이런저런 시도를 해본 결과 아리의 코드가 996ms로 통과했습니다.

i++ 대신 ++i 를 쓰고

뭐 이래저래 삽질을 해야만 겨우겨우 얻을 수 있는 AC네요

포기하고 그냥 std::sort 씁시다.

#include<stdio.h>
#include<algorithm>
using namespace std;
int n, m;
unsigned int a[2][1000009];
unsigned int e[2][1000009];
int b[1000009];
int c[999];
int d[999];
void radix()
{
	int i, j, k;
	for(int dd=0;dd<4;++dd)
	{
		for(i=d[0]=0;i<257;i++)
			c[i]=0;
		for(i=0;i<n;i++)
			c[e[dd%2][i]%256+1]++;
		for(i=1;i<257;i++)
			d[i]=d[i-1]+c[i];
		for(i=0;i<n;++i)
		{
			b[d[(e[dd%2][i])%256]++]=i;
        }
		for(i=0;i<n;++i)
		{
			e[(dd%2)^1][i] = e[dd%2][b[i]]/256;
			a[(dd%2)^1][i] = a[dd%2][b[i]];
		}
	}
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		int i, j;
		for(i=0;i<n;++i)
		{
			scanf("%u",&a[0][i]);
			a[0][i]^=2147483648;
			e[0][i]=a[0][i];
		}
		radix();
		scanf("%d",&m);
		while(m--)
		{
			unsigned int k;
			scanf("%u",&k);
			k^=2147483648;
			int l,r,mid;
			l=0;r=n;
			while(l<r)
			{
				mid=(l+r)/2;
				if(a[0][mid] < k)l=mid+1;
				else r=mid;
			}
			printf("%d\n",(l<n&&a[0][l]==k)?1:0);
		}
	}
}

portableangel 9년 전 0

오와..

감사합니다 ㅋㅋㅋㅋ

baekjoon 9년 전 0

996이면 채점 머신의 상황에 따라서 TLE날 수도 있는 시간이네요... 재채점을 한다면...::::::

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

문제

문제

출처

ICPC

헐.. std::sort 내부 과정이 어떻게 되나요?

portableangel 9년 전 0

movie_jo 9년 전 2

pichulia 9년 전 2

portableangel 9년 전 0

baekjoon 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말