結果
問題 | No.2420 Simple Problem |
ユーザー |
|
提出日時 | 2024-01-14 19:49:33 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 604 ms / 2,000 ms |
コード長 | 5,452 bytes |
コンパイル時間 | 6,011 ms |
コンパイル使用メモリ | 315,548 KB |
実行使用メモリ | 9,600 KB |
最終ジャッジ日時 | 2024-09-28 02:05:56 |
合計ジャッジ時間 | 24,850 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using ll = long long;using ld = long double;using st = string;using mint = atcoder::modint998244353;using Mint = atcoder::modint1000000007;#define vl vector<ll>#define vvl vector<vector<ll>>#define vd vector<ld>#define vvd vector<vector<ld>>#define vb vector<bool>#define vvb vector<vector<bool>>#define vs vector<string>#define vp vector<pair<ll,ll>>#define vvp vector<vector<pair<ll,ll>>>#define vm vector<mint>#define vvm vector<vector<mint>>#define vM vector<Mint>#define vvM vector<vector<Mint>>#define chmax(n,v) n=n<v?v:n#define chmin(n,v) n=n>v?v:n#define all(n) begin(n),end(n)#define nxp(a) next_permutation(all(a))#define rev(n) reverse(all(n))#define sor(n) stable_sort(all(n))#define rep(i,n) for(ll i=0;i<(n);++i)#define reprev(i,n) for(ll i=n-1;0<=i;--i)#define rrep(i,a,n) for(ll i=a;i<(n);++i)#define sz(n) n.size()#define bit(n,shift) ((n&(1<<shift))!=0)#define yn(x) cout << (x?"Yes":"No") << endl;#define lb(a,n) lower_bound(a.begin(),a.end(),n)-a.begin()#define ub(a,n) upper_bound(a.begin(),a.end(),n)-a.begin()#define lb2(a,n) *lower_bound(a.begin(),a.end(),n)#define ub2(a,n) *upper_bound(a.begin(),a.end(),n)template <typename T> void input(T &a) { cin >> a; };template <typename T1, typename... T2> void input(T1&a, T2 &...b) { cin >> a; input(b...); };const ll inf = 1e18;//std::setprecision(13); 出力桁を増やす//2^29<10^9ll di[8]={1,-1,0,0,1,1,-1,-1};ll dj[8]={0,0,1,-1,1,-1,-1,1};//ll da[4]={1,1,-1,-1};//ll db[4]={1,-1,-1,1};//ll na[4]={1,0,1,0};//ll nb[4]={0,1,0,1};template<typename T = ll>vector<T> rd(size_t n) {vector<T> ts(n);for (size_t i = 0; i < n; i++) cin >> ts[i];return ts;}bool is_prime(ll N) {if (N == 1) return false;for (ll i = 2; i * i <= N; ++i) {if (N % i == 0) return false;}return true;}int calc_digit(ll N){int res = 0;while(N>0){res++;N/=10;}return res;}ll factorial(ll n, ll mod = 1e18) {ll ans = 1;for(ll i = n; i >= 2; i--) ans = (ans * i) % mod;return ans;}void printl(vl v){ll vsz=v.size();for(ll i=0;i<vsz;i++){cout << v[i] << endl;}}void prints(vs v){ll vsz=v.size();for(ll i=0;i<vsz;i++){cout << v[i] << endl;}}ll round_up(ll x,ll y){return (x+y-1)/y;}bool in_out(ll x,ll y,ll h,ll w){return 0<=x and x<h and 0<=y and y<w;}struct UnionFind{vector<ll> par;vector<ll> size;UnionFind(ll n){par.resize(2*(n+1),-1);size.resize(2*(n+1),1);}ll root(ll x){if (par[x]==-1) return x;return par[x]=root(par[x]);}void unite(ll u,ll v){ll uu=root(u),vv=root(v);if(uu==vv){return;}if(size[uu]<size[vv]){par[uu]=vv;size[vv]+=size[uu];}else{par[vv]=uu;size[uu]+=size[vv];}return;}bool same(ll u,ll v){return root(u)==root(v);}ll out_size(ll n){return size[n];}};const int MAX = 510000;mint fac[MAX], finv[MAX], inv[MAX];// テーブルを作る前処理void COMinit() {const int MOD = mint::mod();fac[0] = fac[1] = 1;finv[0] = finv[1] = 1;inv[1] = 1;for (int i = 2; i < MAX; i++){fac[i] = fac[i - 1] * i;inv[i] = MOD - inv[MOD%i] * (MOD / i);finv[i] = finv[i - 1] * inv[i];}}// 二項係数計算mint COM(int n, int k){if (n < k) return 0;if (n < 0 || k < 0) return 0;return fac[n] * finv[k] * finv[n - k];}vector<pair<ll, ll>> prime_factorize(ll N){vector<pair<ll, ll> > res;for (ll a = 2; a * a <= N; ++a) {if (N % a != 0) continue;ll ex = 0;while (N % a == 0) {ex++;N /= a;}res.push_back({a, ex});}if (N != 1) res.push_back({N, 1});return res;}vl p_list(ll n){vl res;vb check(n+1);for(ll i=2;i<=n;i++){if(check[i]) continue;res.push_back(i);ll ii=i;while(ii<=n){check[ii]=true;ii+=i;}}return res;}ll sum_v(vl a){ll res=0;ll n=sz(a);rep(i,n) res+=a[i];return res;}vl cumulative_sum(vl a){ll s=sz(a);vl b(s+1,0);for(ll i=0;i<s;i++){b[i+1]=a[i]+b[i];}return b;}ll floor(ll x,ll m){ll r=(x%m+m)%m; //負の剰余を正の剰余に置き換えるreturn (x-r)/m;}ll bubble_sort(vl& a,ll& n){ll res=0;rep(i,n-1){for(ll j=n-1;j>i;j--){if(a[j-1]>a[j]){swap(a[j-1],a[j]);res++;}}}return res;}ll bi_search(unsigned &a,unsigned &b){unsigned ng=2,ok=70000;while(ok-ng>1){unsigned mid=(ok+ng)/2;unsigned y=(mid*mid)-a-b;if(4*a*b<y*y&&mid*mid>a+b) ok=mid;else ng=mid;}return ok;}int main(void) {int N;cin >> N;for(int i = 0; i < N; i++){uint64_t A, B, mid;cin >> A >> B;int ok = 70000, ng = 2;while (abs(ok - ng) > 1) {mid = (ok + ng) / 2;uint64_t Y = ((mid * mid) - A - B);if (4 * A * B < Y * Y && mid * mid > A + B) {ok = mid;} else {ng = mid;}}cout << ok << endl;}}