2022-08-15T13:44:13.333Z

0

감사합니다.. 이 문제는 long long 범위를 초과해서 나타난 문제였네요.. INF 범위를 줄여서 다시 제출했는데 2퍼에서 여전히 터지네요.. 이 문제가 아닌가 봅니다ㅠㅠ

0

그게 아니죠. 이 코드 자체가 초기 공격력이 넘쳤을 때를 대응을 못하는 거잖아요. 디버깅을 해보면 mid가 이상하게 가는 걸 볼 수가 있어요. 

#include<bits/stdc++.h>
using namespace std;
int n, atk;
long long ans = 0;
vector<tuple<int, int, int>> v;
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> atk;
	for (int i = 0; i < n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v.push_back({ a,b,c });
	}
	long long sum = 0;
	for(int i=0;i<n;i++){
		int info, atk1, h; // 정보 , 공격력 ,체력 
		tie(info, atk1, h) = v[i];

		if (info == 1) {
			long long l = 0, r = 1e18+4, mid;
			long long cnt = 1e18+4;
			while (l <= r) {
				mid = (l + r) >> 1;
				if (mid * atk >= h) {
					cnt = min(cnt, mid);
					r = mid - 1;
				}
				else l = mid + 1;
                cout << mid << '\n';
			} 
			sum += (cnt - 1) * atk1;
			//if (i == n - 1) sum++;
		}
		else {
			//sum++;
			if (ans < sum+1) ans = sum + 1;
			if (sum > h) sum -= h;
			else sum = 0;
			atk += atk1;
		}
		//cout << sum << endl;
	}
	if (ans < sum+1) ans = sum + 1;
	cout << ans;
}
/*
1 100 1 1 1
500000000000000000
750000000000000000
625000000000000000
*/

0

1e18을 1e13으로 줄이니깐 mid 값 찍어보니깐 제대로 가는거 같은데, 

이게 잘못된걸까요? 알고리즘 자체가 틀린건지.. ㅠㅠ

0

mid는 때리는 횟수 아닌가요? 초기공격력이 100인데 한번때리면 되는데 지금 보시면 mid가 증가되고 있는데 이상하게 되는 거 아닌가요? 

0

r의 값을 1e13으로 줄이면 mid가 감소하면서 1로 나옵니다! r을 1e18로 크게 잡다보니 mid x (용사 공격력) 이 long long 범위를 초과해서 이상하게 나온거 같은데.. 맞는지는 모르겠습니다

원래 그냥 몇번을 때릴지 구하려면  for문 한번으로 구하면 O(n)인데 그럼 n^2으로 시간초과가 나서 이걸 logn에 구하기 위해서 이분탐색을 썻습니다.

0

네 long long 을 초과해서 그렇게 되는 거구요. 1,000,000이 용사의 최대 초기공격력이라 이 코드가지고는 long long 범위를 무조건 초과해서 안 될 것같아요. 

0

아 알고리즘을 다르게 짜서 풀어보겠습니다.  답변 감사합니다.