結果
| 問題 |
No.2420 Simple Problem
|
| コンテスト | |
| ユーザー |
 yurina256
|
| 提出日時 | 2023-08-12 15:22:40 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,357 bytes |
| コンパイル時間 | 12,929 ms |
| コンパイル使用メモリ | 495,464 KB |
| 実行使用メモリ | 17,224 KB |
| 最終ジャッジ日時 | 2024-11-20 01:42:05 |
| 合計ジャッジ時間 | 106,080 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 2 WA * 1 TLE * 30 |
ソースコード
#include<bits/stdc++.h>
#include <atcoder/all>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/rational.hpp>
using namespace std;
namespace mp = boost::multiprecision;
using Real1024 = mp::number<mp::cpp_dec_float<1024>>;
Real1024 eps = mp::pow((Real1024)10,(Real1024)-12);
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define length size()
//#define int long long
#define ll long long
constexpr ll inf = 1001001001001001001ll;
constexpr ll mod = /* 1000000007*/ 998244353;
constexpr double pi = 3.141592653589793;
//小数出力
//cout << std::setprecision(12);
//imos
void to_ruiseki(vector<int> &vec){
for(int i=1;i<(int)vec.size();i++){
vec[i] += vec[i-1];
}
}
void to_2druiseki(vector<vector<int>> &vec){
rep(i,vec.size()){
rep(j,vec[0].size()){
int s = 0;
if(i!=0) s += vec[i-1][j];
if(j!=0) s += vec[i][j-1];
if(i!=0 && j!=0) s -= vec[i-1][j-1];
s += vec[i][j];
vec[i][j] = s;
}
}
}
//modpow(a,n,mod)
int modpow(int a, int n, int mod) {
long long res = 1;
while (n > 0) {
if (n & 1) res = res * a % mod;
a = a * a % mod;
n >>= 1;
}
return res;
}
//素因数分解
vector<pair<int,int>> p_fact(int N) {
vector<pair<int,int>> res;
for (int a = 2; a * a <= N; ++a) {
if (N % a != 0) continue;
int ex = 0; // 指数
// 割れる限り割り続ける
while (N % a == 0) {
++ex;
N /= a;
}
// その結果を push
res.push_back({a, ex});
}
// 最後に残った数について
if (N != 1) res.push_back({N, 1});
return res;
}
//ctoi
int ctoi(const char c){
switch(c){
case '0': return 0;
case '1': return 1;
case '2': return 2;
case '3': return 3;
case '4': return 4;
case '5': return 5;
case '6': return 6;
case '7': return 7;
case '8': return 8;
case '9': return 9;
default : throw runtime_error("hoge");
}
}
//max
template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
//min
template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
//print
void print() { cout << '\n'; }
template<typename T>
void print(const T &t) { cout << t << '\n'; }
template<typename Head, typename... Tail>
void print(const Head &head, const Tail &... tail) {
cout << head << ' ';
print(tail...);
}
//join
template<typename T> string join(vector<T> &vec ,const string &sp){
int si = vec.length;
if(si==0){
return "";
}else{
stringstream ss;
rep(i,si-1){
ss << vec[i] << sp;
}
ss << vec[si - 1];
return ss.str();
}
}
//木の直径
int tree_diameter(vector<vector<int>> &vec){
//0-indexed
queue<pair<int,int>> que;
vector<bool> is_searched(vec.size(),false);
que.push(make_pair(0,0));
int max_d = 0;
int max_e = 0;
while(!que.empty()){
int e = que.front().first;
int distance = que.front().second;
is_searched[e] = true;
if(max_d<distance){
max_d = distance;
max_e = e;
}
que.pop();
rep(i,vec[e].size()){
if(!is_searched[vec[e][i]]){
que.push( make_pair( vec[e][i], distance + 1 ) );
}
}
}
fill(is_searched.begin(),is_searched.end(),false);
que.push(make_pair(max_e,0));
max_d = 0;
max_e = 0;
while(!que.empty()){
int e = que.front().first;
int distance = que.front().second;
is_searched[e] = true;
if(max_d<distance){
max_d = distance;
max_e = e;
}
que.pop();
rep(i,vec[e].size()){
if(!is_searched[vec[e][i]]){
que.push( make_pair( vec[e][i], distance + 1 ) );
}
}
}
return max_d;
}
//uf 根:root(x) 判定:issame(x,y) 結合:unite(x,y) 大きさ:size(x)
int getlongpath(vector<vector<int>> &vec,int st){
queue<pair<int,int>> que;
vector<bool> is_searched(vec.size(),false);
is_searched[st] = true;
que.push(make_pair(st,0));
int max_d = 0;
int max_e = 0;
while(!que.empty()){
int e = que.front().first;
int distance = que.front().second;
if(max_d<distance){
max_d = distance;
max_e = e;
}
que.pop();
rep(i,vec[e].size()){
if(!is_searched[vec[e][i]]){
que.push( make_pair( vec[e][i], distance + 1 ) );
is_searched[vec[e][i]] = true;
}
}
}
fill(is_searched.begin(),is_searched.end(),false);
que.push(make_pair(max_e,0));
return max_d;
}
struct UnionFind {
vector<int> par, rank, siz;
// 構造体の初期化
UnionFind(int n) : par(n,-1), rank(n,0), siz(n,1) { }
// 根を求める
int root(int x) {
if (par[x]==-1) return x; // x が根の場合は x を返す
else return par[x] = root(par[x]); // 経路圧縮
}
// x と y が同じグループに属するか (= 根が一致するか)
bool issame(int x, int y) {
return root(x)==root(y);
}
// x を含むグループと y を含むグループを併合する
bool unite(int x, int y) {
int rx = root(x), ry = root(y); // x 側と y 側の根を取得する
if (rx==ry) return false; // すでに同じグループのときは何もしない
// union by rank
if (rank[rx]<rank[ry]) swap(rx, ry); // ry 側の rank が小さくなるようにする
par[ry] = rx; // ry を rx の子とする
if (rank[rx]==rank[ry]) rank[rx]++; // rx 側の rank を調整する
siz[rx] += siz[ry]; // rx 側の siz を調整する
return true;
}
// x を含む根付き木のサイズを求める
int size(int x) {
return siz[root(x)];
}
};
vector<pair<long long, long long> > prime_factorize(long long N) {
vector<pair<long long, long long> > res;
for (long long a = 2; a * a <= N; ++a) {
if (N % a != 0) continue;
long long ex = 0; // 指数
// 割れる限り割り続ける
while (N % a == 0) {
++ex;
N /= a;
}
// その結果を push
res.push_back({a, ex});
}
// 最後に残った数について
if (N != 1) res.push_back({N, 1});
return res;
}
class BIT
{
public:
BIT() = default;
// 長さ size の数列で初期化
explicit BIT(size_t size)
: m_bit(size + 1) {}
// 数列で初期化
explicit BIT(const std::vector<long long>& v)
: BIT(v.size())
{
for (int i = 0; i < (int)v.size(); ++i)
{
add((i + 1), v[i]);
}
}
// 閉区間 [1, r] の合計を返す (1-based indexing)
long long sum(int r) const
{
long long ret = 0;
for (; 0 < r; r -= (r & -r))
{
ret += m_bit[r];
}
return ret;
}
// 閉区間 [l, r] の合計を返す (1-based indexing)
long long sum(int l, int r) const
{
return (sum(r) - sum(l - 1));
}
// 数列の i 番目の要素を加算 (1-based indexing)
void add(int i, long long value)
{
for (; i < (int)m_bit.size(); i += (i & -i))
{
m_bit[i] += value;
}
}
private:
std::vector<long long> m_bit;
};
// Binary Indexed Tree (1.2 区間加算対応)
// 1-based indexing
class BIT_RAQ
{
public:
BIT_RAQ() = default;
explicit BIT_RAQ(size_t size)
: m_bit0(size)
, m_bit1(size) {}
explicit BIT_RAQ(const std::vector<long long>& v)
: m_bit0(v)
, m_bit1(v.size()) {}
// 閉区間 [1, r] の合計を返す (1-based indexing)
long long sum(int r) const
{
return (m_bit0.sum(r) + m_bit1.sum(r) * r);
}
// 閉区間 [l, r] の合計を返す (1-based indexing)
long long sum(int l, int r) const
{
return (sum(r) - sum(l - 1));
}
// 数列の i 番目の要素を加算 (1-based indexing)
void add(int i, long long value)
{
m_bit0.add(i, value);
}
// 閉区間 [l, r] の要素を加算 (1-based indexing)
void add(int l, int r, long long value)
{
m_bit0.add(l, (-value * (l - 1)));
m_bit0.add((r + 1), (value * r));
m_bit1.add(l, value);
m_bit1.add((r + 1), -value);
}
private:
BIT m_bit0;
BIT m_bit1;
};
int bs(vector<pair<int,int>> &vec,int n){
int left = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
int right = (int)vec.size(); // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()
/* どんな二分探索でもここの書き方を変えずにできる！ */
while (right - left > 1) {
int mid = left + (right - left) / 2;
if (n <= vec[mid].second) right = mid;
else left = mid;
}
/* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
return (int)(right < (int)vec.size() && vec[right].first <= n);
}
signed main(void){
int n;
cin >> n;
rep(p,n){
Real1024 a,b,c;
cin >> a >> b;
c = mp::sqrt(a)+mp::sqrt(b);
if(mp::abs(c-mp::ceil(c))<eps) cout << mp::ceil(c+(Real1024)1) << endl;
else cout << mp::ceil(c) << endl;
//cout << mp::ceil(c-eps) << endl;
}
}