結果

問題 No.550 夏休みの思い出（１）
コンテスト
ユーザー tnakao0123
提出日時 2017-07-31 18:32:57
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 1,810 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 781 ms
コンパイル使用メモリ 85,848 KB
実行使用メモリ 13,824 KB
最終ジャッジ日時 2024-10-11 00:10:33
合計ジャッジ時間 7,285 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 54
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

/* -*- coding: utf-8 -*-
 *
 * 550.cc: No.550 夏休みの思い出(1) - yukicoder
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

/* typedef */

typedef long long ll;

/* global variables */

/* subroutines */

/* main */

// f(x)=(x-a)(x-b)(x-c) = x^3+Ax^2+Bx+C = 0
// -> (x^2-(a+b)x+ab)(x-c) = x^3-(a+b+c)x^2+(ab+bc+ca)x-abc = 0
// A=-(a+b+c) -> -(b+c)=A+a, C=-abc -> bc=-C/a

int main() {
  ll A, B, C;
  cin >> A >> B >> C;

  ll a;
  for (a = -1000000; a <= 1000000; a++) {
    ll y = a * a * a + A * a * a + B * a + C;
    if (y == 0) break;
  }
  //printf("a=%lld\n", a);

  ll D = A + a, E = (a != 0) ? -C / a : B;
  //printf("x^2+%lldx+%lld\n", D, E);

  ll x0 = -1000000, x1 = 1000000, y0, y1;
  for (;;) {
    y0 = x0 * x0 + D * x0 + E;
    y1 = x1 * x1 + D * x1 + E;
    if (y0 <= 0 || y1 <= 0) break;
    ll x = (x0 + x1) / 2;
    if (y0 > y1) x0 = x;
    else x1 = x;
  }
  //printf("x0=%lld, x1=%lld\n", x0, x1);

  ll b;
  if (y0 == 0) b = x0;
  else if (y1 == 0) b = x1;
  else if (y0 < 0) {
    while (x0 + 1 < x1) {
      ll x = (x0 + x1) / 2;
      ll y = x * x + D * x + E;
      if (y > 0) x1 = x;
      else x0 = x;
    }
    b = x0;
  }
  else {
    while (x0 + 1 < x1) {
      ll x = (x0 + x1) / 2;
      ll y = x * x + D * x + E;
      if (y > 0) x0 = x;
      else x1 = x;
    }
    b = x1;
  }
  ll c = -(D + b);
  //printf("b=%lld, c=%lld\n", b, c);

  ll v[3];
  v[0] = a, v[1] = b, v[2] = c;
  sort(v, v + 3);

  printf("%lld %lld %lld\n", v[0], v[1], v[2]);
  return 0;
}
0