Submission #3225432


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define each(i,a) for (auto&& i : a)
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)

const ll linf = 1e18;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
  each(x,vec) is >> x;
  return is;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
  rep(i,vec.size()) {
    if (i) os << " ";
    os << vec[i];
  }
  return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector< vector<T> >& vec) {
  rep(i,vec.size()) {
    if (i) os << endl;
    os << vec[i];
  }
  return os;
}

// ll solve_naive(ll A, ll B) {
//   ll ans = 0;

//   return ans;
// }
ll solve(ll A, ll B) {
  if (A == 1 && B == 1) return 0;
  // if (A * B <= 30000) return solve_naive(A, B);
  ll ans = 0;
  ll C = A * B - 1;
  ans += sqrt(C);
  ll i = sqrt(C);
  ll j = C / i;
  ll pi = i, pj = C / i;
  if (A <= i) --ans;
  for (ll t = 0; j > 0 && t < 5; --j, ++t) {
    i = C / j;
    if (i == pi || i == 0) continue;
    if (j == B) continue;
    pj = j;
    pi = i;
    ++ans;
  }
  if (B <= j) --ans;
  if (j > 0) ans += j;
  return ans;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll Q; cin >> Q;
  rep(q, Q) {
    ll A, B; cin >> A >> B;
    cout << solve(A, B) << endl;
  }
}

Submission Info

Submission Time
Task D - Worst Case
User drafear
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1952 Byte
Status WA
Exec Time 1 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 1
AC × 5
WA × 7
Set Name Test Cases
Sample s1.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, s1.txt
Case Name Status Exec Time Memory
01.txt AC 1 ms 256 KB
02.txt WA 1 ms 256 KB
03.txt WA 1 ms 256 KB
04.txt AC 1 ms 256 KB
05.txt AC 1 ms 256 KB
06.txt WA 1 ms 256 KB
07.txt WA 1 ms 256 KB
08.txt WA 1 ms 256 KB
09.txt WA 1 ms 256 KB
10.txt WA 1 ms 256 KB
11.txt AC 1 ms 256 KB
s1.txt AC 1 ms 256 KB