結果

問題 No.550 夏休みの思い出（１）
ユーザー minami
提出日時 2017-07-28 22:48:19
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,292 bytes
コンパイル時間 2,131 ms
コンパイル使用メモリ 181,204 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-11 05:30:53
合計ジャッジ時間 3,579 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 55
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

using ld = long double;
const double eps = 1e-8;

ld bisection_method(ld x0, ld x1, std::function<ld(ld)> f) {
	ld y0 = f(x0), y1 = f(x1), m;
	int s0 = std::abs(y0) < eps ? 0 : y0 < 0 ? -1 : 1;
	int s1 = std::abs(y1) < eps ? 0 : y1 < 0 ? -1 : 1;
	assert(s0 * s1 <= 0);
	if (y0 > y1) std::swap(x0, x1);
	for (int i = 0; i < 200; i++) {
		m = (x0 + x1) / 2;
		if (f(m) > 0)
			x1 = m;
		else
			x0 = m;
	}
	return m;
}

std::vector<ld> quadratic_equation(ld a, ld b, ld c) {
	ld d = b * b - 4 * a * c;
	if (std::abs(a) < eps) return std::abs(b) > eps ? std::vector<ld>{-c / b} : std::vector<ld>{};
	if (d < -eps) return{};
	if (d < eps) return{ -b / (2 * a), -b / (2 * a) };
	int sign = (b >= 0) ? 1 : -1;
	ld x0 = (-b - sign * sqrt(std::abs(d))) / (2 * a), x1 = c / (a * x0);
	if (x0 > x1) std::swap(x0, x1);
	return{ x0, x1 };
}

std::vector<ld> cubic_equation(ld a, ld b, ld c, ld d) {
	if (std::abs(a) < eps) return quadratic_equation(b, c, d);
	if (a < 0) a = -a, b = -b, c = -c, d = -d;
	static const ld INF = 1e9;
	ld x0 =
		bisection_method(-INF, INF, [&](ld x) { return a * x * x * x + b * x * x + c * x + d; });
	ld aa = 1, bb = b / a + x0, cc = c / a + bb * x0;
	auto res = quadratic_equation(aa, bb, cc);
	res.push_back(x0);
	std::sort(res.begin(), res.end());
	return res;
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int a, b, c; cin >> a >> b >> c;
	auto w = cubic_equation(1, a, b, c);
	sort(all(w));
	vector<int> v;
	rep(i, -1, 2) {
		rep(j, 0, 3) {
			int x = w[j] + i;
			if (x*x*x + a*x*x + b*x + c == 0)
				v.push_back(x);
		}
	}
	sort(all(v));
	v.erase(unique(v.begin(), v.end()), v.end());
	cout << v[0]; rep(i, 1, v.size()) { cout << " " << v[i]; } cout << endl;
	return 0;
}
0