글 읽기 - 시간 초과 이유를 모르겠습니다.

leechhe 8년 전 0

N <= 2000이고 |Ai| < 1,000,000,000 이고

시간복잡도가 N^2log|Ai|라고 생각해서 괜찮을거라고 생각했는데 아닌가요?

#include <cstdio>
#include <map>
#include <utility>
using namespace std;
typedef pair<int, int> intPair;
int seq[2000];
int main(){
    int n; scanf("%d",&n);
    map<int, int> m;
    for( int i = 0 ; i < n ; ++i ){
        scanf("%d",&seq[i]);
        m.insert(make_pair(seq[i], 1));
    }
    int ret = 0;
    for( int i = 0 ; i < n-1 ; ++i ){
        for( int j = i+1 ; j < n ; ++j ){
            if( seq[i] == seq[j] ) continue;
            if (m[seq[i]+seq[j]]) {
                m[seq[i]+seq[j]] = 0;
                ++ret;
            }
        }
    }
    printf("%d", ret);
    return 0;
}

dotorya 8년 전 1

map이 logN중 가장 느린 편이긴 합니다 ㅠㅠ

제 컴퓨터에서 map에 400만개를 넣는 소스가 919ms 걸리네요. (아래 소스입니다.)

그리고 이 문제는 N^2짜리 알고리즘이 있습니다.

더 좋은 알고리즘을 찾아보는 것도 괜찮을 것 같습니다!

int main() {
	int st = clock();
	map <int, int> Mx;
	for (int i = 1; i <= 4000000; i++) Mx[i] = i;
	printf("%d\n", clock() - st);
	return 0;
}

insu_nym 8년 전 0

창희 형 얼른 주무세요

leechhe 8년 전 0

@dotorya 감사합니다 고민해볼게요! 다시 생각해보니 N^2logN같은데... 그래도 왜 터지는지는 모르겠네여 ㅠㅠ

@insu_nym 창피하게 이러지마

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

문제

문제

출처

ICPC

시간 초과 이유를 모르겠습니다.

leechhe 8년 전 0

dotorya 8년 전 1

insu_nym 8년 전 0

leechhe 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말