結果

問題 No.2420 Simple Problem
ユーザー Cyanmond
提出日時 2023-08-12 14:02:37
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 80 ms / 2,000 ms
コード長 13,278 bytes
コンパイル時間 1,702 ms
コンパイル使用メモリ 196,796 KB
最終ジャッジ日時 2025-02-16 04:04:40
ジャッジサーバーID
(参考情報)
judge3 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#line 1 "main.cpp"
#include <bits/stdc++.h>
#line 2 "template.cpp"
#pragma region templates
#pragma region std::vector operator
template <class T>
std::vector<T> &operator++(std::vector<T> &v) {
for (auto &e : v) {
++e;
}
return v;
}
template <class T>
std::vector<T> operator++(std::vector<T> &v, int) {
auto res = v;
for (auto &e : v) {
++e;
}
return res;
}
template <class T>
std::vector<T> &operator--(std::vector<T> &v) {
for (auto &e : v) {
--e;
}
return v;
}
template <class T>
std::vector<T> operator--(std::vector<T> &v, int) {
auto res = v;
for (auto &e : v) {
--e;
}
return res;
}
#pragma endregion
#pragma region ios
namespace scanner {
namespace submodule {
void read(int &a) {
std::cin >> a;
}
void read(long long &a) {
std::cin >> a;
}
void read(char &a) {
std::cin >> a;
}
void read(double &a) {
std::cin >> a;
}
void read(std::string &a) {
std::cin >> a;
}
template <class T, class S>
void read(std::pair<T, S> &p) {
read(p.first);
read(p.second);
}
template <class T>
void read(std::vector<T> &);
template <class T>
void read(std::vector<T> &a) {
for (auto &e : a) {
read(e);
}
}
template <class T>
void read(T &a) {
std::cin >> a;
}
} // namespace submodule
void scan() {}
template <class Head, class... Tail>
void scan(Head &head, Tail &...tail) {
submodule::read(head);
scan(tail...);
}
void scanI() {}
template <class Head, class... Tail>
void scanI(Head &head, Tail &...tail) {
submodule::read(head);
--head;
scanI(tail...);
}
} // namespace scanner
template <class T, class U>
std::ostream &operator<<(std::ostream &os, std::pair<T, U> pa) {
os << '{' << pa.first << ", " << pa.second << '}';
return os;
}
template <class T>
std::ostream &operator<<(std::ostream &os, std::vector<T> vec) {
os << "{";
const int n = (int)vec.size();
for (int i = 0; i < n; i++) {
os << vec[i];
os << (i == n - 1 ? "}" : ", ");
}
return os;
}
template <class T, std::size_t S>
std::ostream &operator<<(std::ostream &os, std::array<T, S> arr) {
os << "{";
for (int i = 0; i < (int)S; i++) {
os << arr[i];
os << (i == S - 1 ? "}" : ", ");
}
os << "}";
return os;
}
template <class T, class U>
std::ostream &operator<<(std::ostream &os, std::map<T, U> ma) {
os << "{";
auto itr = ma.begin();
while (itr != ma.end()) {
os << *itr << (itr == --ma.end() ? "}" : ", ");
++itr;
}
return os;
}
template <class T>
std::ostream &operator<<(std::ostream &os, std::set<T> st) {
os << "{";
auto itr = st.begin();
while (itr != st.end()) {
os << *itr << (itr == --st.end() ? "}" : ", ");
++itr;
}
return os;
}
namespace printer {
void print() {
std::cout << '\n';
}
template <class Head, class... Tail>
void print(const Head &head, const Tail &...tail) {
std::cout << head;
if (sizeof...(tail))
std::cout << ' ';
print(tail...);
}
} // namespace printer
namespace dumper {
void dumpFunc() {
std::cerr << std::endl;
}
template <class Head, class... Tail>
void dumpFunc(Head &&head, Tail &&...tail) {
std::cerr << head;
if (sizeof...(Tail) == 0) {
std::cerr << ' ';
} else {
std::cerr << ", ";
}
dumpFunc(std::move(tail)...);
}
} // namespace dumper
#pragma endregion
#pragma region functions
template <class T>
constexpr int si(const T &c) {
return static_cast<int>(c.size());
}
template <class T>
constexpr bool afMin(T &a, const T &b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template <class T>
constexpr bool afMax(T &a, const T &b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template <class T = long long, class S>
constexpr T calcSum(const S &container) {
return std::accumulate(container.begin(), container.end(), static_cast<T>(0));
}
template <class T>
constexpr auto calcMin(const T &container) {
return *std::min_element(container.begin(), container.end());
}
template <class T>
constexpr auto calcMax(const T &container) {
return *std::max_element(container.begin(), container.end());
}
template <class T>
constexpr int lwbi(const T &container, const typename T::value_type &value) {
return static_cast<int>(std::distance(container.cbegin(), std::lower_bound(container.cbegin(), container.cend(), value)));
}
template <class T>
constexpr int upbi(const T &container, const typename T::value_type &value) {
return static_cast<int>(std::distance(container.cbegin(), std::upper_bound(container.cbegin(), container.cend(), value)));
}
template <class T>
auto makeVec(const int n, const T &value) {
return std::vector(n, value);
}
template <class... Args>
auto makeVec(const int n, Args... args) {
return std::vector(n, makeVec(args...));
}
template <class T, class F>
T binarySearch(T ok, T ng, const F &f) {
while (abs(ok - ng) > 1) {
T mid = ok + ng >> 1;
(f(mid) ? ok : ng) = mid;
}
return ok;
}
template <class T, class F>
T binarySearchReal(T ok, T ng, const F &f, int iter = 80) {
while (iter--) {
T mid = (ok + ng) / 2;
(f(mid) ? ok : ng) = mid;
}
return ok;
}
#pragma endregion
#pragma region macros and vars
using namespace scanner;
using namespace printer;
using i64 = long long;
template <class T>
using Vec = std::vector<T>;
template <class T>
using PQ = std::priority_queue<T>;
template <class T>
using RPQ = std::priority_queue<T, std::vector<T>, std::greater<T>>;
std::mt19937 mtRand(std::random_device{}());
constexpr std::array<std::pair<int, int>, 4> dxy4 = {{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}};
constexpr std::array<std::pair<int, int>, 8> dxy8 = {
{{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}}};
#define INT(...) \
int __VA_ARGS__; \
scan(__VA_ARGS__)
#define INTI(...) \
int __VA_ARGS__; \
scanI(__VA_ARGS__)
#define I64(...) \
i64 __VA_ARGS__; \
scan(__VA_ARGS__)
#define I64I(...) \
i64 __VA_ARGS__; \
scanI(__VA_ARGS__)
#define STR(...) \
std::string __VA_ARGS__; \
scan(__VA_ARGS__)
#define CHR(...) \
char __VA_ARGS__; \
scan(__VA_ARGS__)
#define DOUBLE(...) \
double __VA_ARGS__; \
scan(__VA_ARGS__)
#define VEC(type, name, n) \
std::vector<type> name(n); \
scan(name)
#define VECI(type, name, n) \
std::vector<type> name(n); \
scanI(name)
#define VEC2(type, name1, name2, n) \
std::vector<type> name1(n), name2(n); \
for (int i = 0; i < n; i++) \
scan(name1[i], name2[i])
#define VEC2I(type, name1, name2, n) \
std::vector<type> name1(n), name2(n); \
for (int i = 0; i < n; i++) \
scanI(name1[i], name2[i])
#define VEC3(type, name1, name2, name3, n) \
std::vector<type> name1(n), name2(n), name3(n); \
for (int i = 0; i < n; i++) \
scan(name1[i], name2[i], name3[i])
#define VEC3I(type, name1, name2, name3, n) \
std::vector<type> name1(n), name2(n), name3(n); \
for (int i = 0; i < n; i++) \
scanI(name1[i], name2[i], name3[i])
#define VEC4(type, name1, name2, name3, name4, n) \
std::vector<type> name1(n), name2(n), name3(n), name4(n); \
for (int i = 0; i < n; i++) \
scan(name1[i], name2[i], name3[i], name4[i]);
#define VEC4I(type, name1, name2, name3, name4, n) \
std::vector<type> name1(n), name2(n), name3(n), name4(n); \
for (int i = 0; i < n; i++) \
scanI(name1[i], name2[i], name3[i], name4[i]);
#define VV(type, name, h, w) \
std::vector<std::vector<type>> name(h, std::vector<type>(w)); \
scan(name)
#define VVI(type, name, h, w) \
std::vector<std::vector<type>> name(h, std::vector<type>(w)); \
scanI(name)
#define overload5(a, b, c, d, e, name, ...) name
#define rep(i, l, r) for (int i = (l); i < (r); ++i)
#define per(i, l, r) for (int i = (r - 1); i >= (l); --i)
#define fore0(a) rep (a.size())
#define fore1(i, a) for (auto &&i : a)
#define fore2(a, b, v) for (auto &&[a, b] : v)
#define fore3(a, b, c, v) for (auto &&[a, b, c] : v)
#define fore4(a, b, c, d, v) for (auto &&[a, b, c, d] : v)
#define fore(...) overload5(__VA_ARGS__, fore4, fore3, fore2, fore1, fore0)(__VA_ARGS__)
#define pb push_back
#define eb emplace_back
#define mp std::make_pair
#define ALL(x) (x).begin(), (x).end()
#define UNIQUE(x) (x).erase(std::unique((x).begin(), (x).end()), (x).end())
#define fi first
#define se second
#define dump(...) \
std::cerr << ' '; \
std::cerr << #__VA_ARGS__ << " : [" << __LINE__ << " : " << __FUNCTION__ << "]" << std::endl; \
std::cerr << " "; \
dumper::dumpFunc(__VA_ARGS__)
#pragma endregion
#pragma endregion
#line 4 "main.cpp"
struct MakeIOFast {
MakeIOFast() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout << std::fixed << std::setprecision(15);
}
} makeIOFastv;
using namespace std;
i64 solve(i64 A, i64 B) {
i64 ok = 2 * sqrt(1000000000) + 5, ng = 0;
while (ok - ng > 1) {
const auto m = (ok + ng) / 2;
// sqrt(A)+sqrt(B)<N ?
// A+B+2sqrt(AB)<N^2?
// A+B-N^2<-2sqrt(AB)?
// (A+B-N^2)^2 > 4AB ?
i64 x = A + B - m * m;
i64 y = 4 * A * B;
if (x >= 0) ng = m;
else if (x * x > y) ok = m;
else ng = m;
}
return ok;
}
int main() {
int N;
cin >> N;
while (N--) {
I64(A, B);
print(solve(A, B));
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0