글 읽기 - 시간초과가 왜안나나요?

poirin 6년 전 0

비주얼 스튜디오에서 컴파일할때 3000000 이상 숫자 입력하면 10초가 넘게걸리는데 여기선 28ms라고 뜨고 통과가되네요

왜이런지 잘 모르겠습니다;

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;


int main()
{
	int n;
	int l, r;
	int sum = 0;
	int ans = 0;
	cin >> n;
	vector<bool> v(n + 1);
	vector<int> p;
	
	for (int i = 2; i <= n; i++)
	{
		if (v[i] == false) {
			p.push_back(i);
			for (int j = i*2; j <= n; j += i)
			{
				v[j] = true;
			}
		}
	}

	l = r = 0;
	sum = p.empty() ? 0 : p[0];

	while (r < p.size())
	{
		if (sum <= n)
		{
			r++;
			if (sum == n) ans++;
			if (r < p.size()) {
				sum += p[r];
			}
		}
		else
		{
			sum -= p[l];
			l++;
			if (sum == 0)
			{
				r = l;
			}
		}
	}
	cout << ans;
}

sphist94 5년 전 0

원인은 vector<bool> 때문인데 저도 이것 때문에 헤매다가 그냥 자료형을 bool 배열로 설정하니 빠르게 되네요.

이게 정확한지는 모르겠지만

http://soen.kr/lecture/ccpp/cp...

이 링크에 보시면 vector<bool>은 사용을 자제하는걸 권하고 있네요.(저도 이유는 아직 잘 모르겠습니다.)

sphist94 5년 전 0

이게 맞는지는 모르겠지만, 위의 설명에 따르면

일반적인 bool 은 1바이트의 용량을 차지하지만, vector<bool>은 1비트만 쓰게끔 최적화되어 있는데,

컴파일러마다 지원 범위가 달라서 이런 오류가 발생한 것 같습니다.

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

문제

문제

출처

ICPC

시간초과가 왜안나나요?

poirin 6년 전 0

sphist94 5년 전 0

sphist94 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말