結果
問題 | No.2420 Simple Problem |
ユーザー |
|
提出日時 | 2023-08-12 14:26:01 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 81 ms / 2,000 ms |
コード長 | 3,126 bytes |
コンパイル時間 | 1,975 ms |
コンパイル使用メモリ | 197,060 KB |
最終ジャッジ日時 | 2025-02-16 04:48:34 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; using Pair = pair<int, int>; using Tuple = tuple<int, int, int>; using VI1 = vector<int>; using VI2 = vector<VI1>; using VL1 = vector<ll>; using VL2 = vector<VL1>; using VD1 = vector<ld>; using VD2 = vector<VD1>; using VB1 = vector<bool>; using VB2 = vector<VB1>; using VP1 = vector<Pair>; using VP2 = vector<VP1>; using VT1 = vector<Tuple>; using VT2 = vector<VT1>; using Queue = queue<int>; using DQ = deque<int>; using PQ = priority_queue<int, vector<int>, greater<int>>; using Table = VI2; using Graph = VI2; /** io */ template <typename T> std::vector<T> input_vec(int N); template <typename T> void output_row(std::vector<T> &row); template <typename T> void output_col(std::vector<T> &col); void outputYesNo(bool yes, const string &Yes = "Yes", const string &No = "No"); /** minmax */ template <typename T> bool chmin(T &a, T b); template <typename T> bool chmax(T &a, T b); template <typename T> T calc_floor_sqrt(T n) { assert(n >= T(0)); auto r = sqrtl(n); T i(r); while (i > T(0) && i * i >= n) { --i; } while (i * i <= n) { ++i; } return i - 1; } template <typename T> T calc_ceil_sqrt(T n) { assert(n >= T(0)); auto r = sqrtl(n); T i(r); while (i * i <= n) { ++i; } while (i > T(0) && i * i >= n) { --i; } return i + 1; } bool is_ok(ll A, ll B, ll x) { auto x2 = x * x; auto x4 = x2 * x2; auto C = (A - B) * (A - B); return (x4 - 2 * (A + B) * x2 + C > 0); } auto solve() { int N; cin >> N; VI1 A(N), B(N); for (int i = 0; i < N; ++i) { cin >> A.at(i) >> B.at(i); } VI1 X(N); for (int i = 0; i < N; ++i) { auto Ai = A.at(i), Bi = B.at(i); auto a = calc_floor_sqrt(Ai); auto b = calc_floor_sqrt(Bi); auto x = a + b + 1; while (!is_ok(Ai, Bi, x)) { ++x; } X.at(i) = x; } return X; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int t = 1; // cin >> t; while (t--) { auto result = solve(); // cout << result << '\n'; // output_row(result); output_col(result); // outputYesNo(result, "Yes", "No"); } } /** @note 使用頻度が高く毎回貼付するのが面倒なライブラリを実装しておく。*/ template <typename T> std::vector<T> input_vec(int N) { std::vector<T> v(N); for (auto &vi : v) { cin >> vi; } return v; } void outputYesNo(bool yes, const string &Yes, const string &No) { if (yes) cout << Yes << '\n'; else cout << No << '\n'; } template <typename T> void output_row(std::vector<T> &row) { int N = row.size(); for (int i = 0; i < N; ++i) { if (i > 0) cout << ' '; cout << row.at(i); } cout << '\n'; } template <typename T> void output_col(std::vector<T> &col) { int N = col.size(); for (int i = 0; i < N; ++i) { cout << col.at(i) << '\n'; } } template <typename T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } template <typename T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }