글 읽기 - 어떤 case 에서 틀리는지 모르겠네요 ㅠㅠ

kev0960 8년 전 0

어떤 case 에서 틀리는지 모르겠네요 ㅠㅠ

간단간단한거들은 다 테스트 해보았는데

어디서 틀리는지 모르겟어요 ㅠㅠ

#include <iostream>
#include <vector>
#include <set>
#include <unordered_map>
#include <queue>
#include <cmath>
#include <utility>
using namespace std;

struct Data
{
	long long s;
	long long p;
	long long num;
	long long last;
	
	Data(long long x, long long y, long long z, long long last) : s(x), p(y), num(z), last(last) {}
};
bool operator<(const Data& lhs, const Data& rhs)
{
    return lhs.num > rhs.num;
}

unordered_map<long long , vector<long long> > divisor_map;
vector<long long> P_divisors;

vector<long long> get_divisors(long long x) {
	vector<long long> divisors;
	for(int i = 1; i <= sqrt(x) + 1; i ++) {
		if(x % i == 0) {
			divisors.push_back(i); divisors.push_back(x / i);
		}
	}
	divisor_map[x] = divisors;
//	cout << "job done :: " << divisors.size() <<  endl;
	return divisors;
}
// 약수를 빨리 구한다.
vector<long long> fast_divisors(long long P, long long x) {
	unordered_map<long long , vector<long long> >::iterator itr = divisor_map.find(x);
	if(itr != divisor_map.end()) return itr->second;
	
	vector<long long> divisors;
	long long d = P / x;
	for(int i = 0; i < P_divisors.size(); i ++) {
		if(P_divisors[i] % d == 0) {
			divisors.push_back(P_divisors[i] / d);
		}
	}
	divisor_map[x] = divisors;
	return divisors;
}

int main() {
	long long S, P;
	cin >> S >> P;
	
	set<pair<long long, long long>> list;
	priority_queue<Data> q;
	
	q.push(Data(S, P, 0, 0));
	long long current_min = 1000000001;
	
	P_divisors = get_divisors(P);
	
	while (!q.empty()) {
		Data x = q.top();
		q.pop();
	
		if(x.num > current_min) continue;
		
		if(x.p == 1) { // 나머지는 1 로 채움
			long long num = x.num + x.s;
			if(num < current_min) {
				current_min = num;
			}
			continue; 
		}
		vector<long long> divs = fast_divisors(P, x.p); 

		for(int i = 0; i < divs.size(); i ++) {
			if(divs[i] == 1) continue;
			if(x.s == divs[i] && x.p == divs[i]) { cout << x.num + 1 << endl; return 0; }
			else if(x.s > divs[i] && divs[i] >= x.last) {
				Data t(x.s - divs[i], x.p / divs[i], x.num + 1, divs[i]);
			    
				if(list.find(make_pair(t.s, t.p)) != list.end()) { continue; }
				else list.insert(make_pair(t.s, t.p));

				q.push(t);
			}
		}
	}
	if(current_min != 1000000001) cout << current_min << endl;
	else cout << -1 << endl;
	return 0;
}

portableangel 8년 전 1

이 문제 아마 리스트에 들어있는 수가 정수가 아니라 실수가 될 수도 있는 것 같습니다.

@baekjoon 문제 원문이나 데이터를 확인해주실 수 있을까요?

baekjoon 8년 전 1

수정했습니다.

kev0960 8년 전 0

헐 ㅠㅠ

괜히 엄청 삽질했네요 ㅜㅜ

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

문제

문제

출처

ICPC

어떤 case 에서 틀리는지 모르겠네요 ㅠㅠ

kev0960 8년 전 0

portableangel 8년 전 1

baekjoon 8년 전 1

kev0960 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말