글 읽기 - 제곱 ㄴㄴ ㅠㅠ

01234 1년 전 0

런타임 뜨네요.

왜 그런지 모르겠어요//

으아아아아아아아아아아앙

혹시 si범위 일까요?

아니면 다른거인가요? si는 늘려도 계속 런타임이에요 ㅠㅠ

#include <iostream>
#include <vector>
#include <cmath>
#define ll long long
using namespace std;
ll k;
bool si[100000001]={false};
ll sqnum(long long ma) {


	long long ans = ma; 
	ll i;
	for(i=0;i*i<=ma;i++) si[i]=false;
	i = 2; 
	while (i * i <= ma) {
        ll s=1;
		while (s * (i * i) <= ma) {
			if (si[s * (i * i) - 1] == false) {
				si[s * (i * i) - 1] = true;
				ans -= 1;
			}
			s+= 1;
		}
		i += 1; 
	}
	return ans;
}
int main()
{
	ll s,e,t,mid;
	s=1;
	cin>>t;
	e=2*t;
	while(s<=e)
	{
		mid=(s+e)/2;
		if(sqnum(mid)<t)
		{
			s=mid+1;
		}
		else e=mid-1;
	}
	cout<<s;
}

djm03178 1년 전 0

주어지는 수는 10억 이하이므로 18, 19번째 줄에서도 10억 번째 인덱스에 접근할 수 있는데, si의 크기는 1억밖에 안 됩니다.

0000000000 1년 전 0

사실 1억은 OOB로 RTE가 나지만 10억은 MLE가 날 겁니다

다른 방법을 생각해 보세요

01234 1년 전 0

ㅠㅠ 루트 ma 로 해도 안되요 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

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

문제

문제

출처

ICPC

제곱 ㄴㄴ ㅠㅠ

01234 1년 전 0

djm03178 1년 전 0

0000000000 1년 전 0

01234 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말