글 읽기 - 시간초과가 납니다

jungin0507 3년 전 0

26번 줄에서 if(x<=0)으로 고치면 통과가 되긴합니다.

그런데 func함수의 인자에 음수가 들어갈 수가 있나요?

어떤 수가 있다했을때 MSB를 뺀 수를 구하기 위해서

x - 2^(log x)를 해줬는데 func 함수 인자가 음수가 될 수 있다는 말은 저 값이 음수가 된다는건데 아무리 생각해도 그런 x값은 존재하지가 않습니다.

어째서 26번 줄을 if(x==0)에서 if(x<=0)으로 고쳐야만 통과하는걸까요?

또, 2^(log x)는 항상 10000...이기 때문에

처음에는 34번 줄에서 x xor 2^(log x)로 연산을 했었는데 이거 역시 무한루프를 도는 케이스가 있습니다. 어떤 x값이 들어오면 무한루프를 돌게 되는걸까요?

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>

#define MAX 105
#define pii pair<int, int>
#define INF 987654321
#define vi vector<int>
#define sq(x) ((x) * (x))

typedef long long ll;

using namespace std;

ll A, B;

ll func(ll x) {
	if (x == 0) return 0;
	if (x == 1) return 1;
	int logx = (int)log2(x);
	ll lower = (1 << (logx)) - 1;
	ll ret = 0;

	ret += (1 << (logx - 1)) * logx;
	ret += x - lower;
	ret += func(x - (1 << logx));

	return ret;
}

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> A >> B;

	cout << func(B) - func(A - 1) << "\n";
}

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

문제

문제

출처

ICPC

시간초과가 납니다

jungin0507 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말