結果
問題 | No.2953 Maximum Right Triangle |
ユーザー |
|
提出日時 | 2024-11-08 22:12:30 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 18,566 bytes |
コンパイル時間 | 2,884 ms |
コンパイル使用メモリ | 212,452 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-08 22:12:39 |
合計ジャッジ時間 | 3,409 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 6 |
ソースコード
#ifndef MATH_FLOOR_CEIL_HPP#define MATH_FLOOR_CEIL_HPP 1#include <cassert>namespace kk2 {// floor(x) = ceil(x) - 1 (for all x not in Z) ...(1)// floor(x) = -ceil(-x) (for all x) ...(2)// return floor(a / b)template <typename T, typename U> constexpr T fracfloor(T a, U b) {assert(b != 0);if (a % b == 0) return a / b;if (a >= 0) return a / b;// floor(x) = -ceil(-x) by (2)// = -floor(-x) - 1 by (1)return -((-a) / b) - 1;}// return ceil(a / b)template <typename T, typename U> constexpr T fracceil(T a, U b) {assert(b != 0);if (a % b == 0) return a / b;if (a >= 0) return a / b + 1;// ceil(x) = -floor(-x) by (2)return -((-a) / b);}} // namespace kk2#endif // MATH_FLOOR_CEIL_HPP// #include <kk2/math/frac_floor.hpp>#ifndef TEMPLATE#define TEMPLATE 1// #pragma GCC optimize("O3,unroll-loops")// #include <bits/stdc++.h>#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <chrono>#include <cmath>#include <cstring>#include <deque>#include <fstream>#include <functional>#include <iomanip>#include <iostream>#include <iterator>#include <limits>#include <map>#include <numeric>#include <optional>#include <queue>#include <random>#include <set>#include <sstream>#include <stack>#include <string>#include <tuple>#include <type_traits>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>#ifndef TYPE_TRAITS_HPP#define TYPE_TRAITS_HPP 1#include <istream>#include <ostream>#include <type_traits>namespace kk2 {template <typename T>using is_signed_int128 = typename std::conditional<std::is_same<T, __int128_t>::valueor std::is_same<T, __int128>::value,std::true_type,std::false_type>::type;template <typename T>using is_unsigned_int128 =typename std::conditional<std::is_same<T, __uint128_t>::valueor std::is_same<T, unsigned __int128>::value,std::true_type,std::false_type>::type;template <typename T>using is_integral =typename std::conditional<std::is_integral<T>::value or is_signed_int128<T>::valueor is_unsigned_int128<T>::value,std::true_type,std::false_type>::type;template <typename T>using is_signed = typename std::conditional<std::is_signed<T>::value or is_signed_int128<T>::value,std::true_type,std::false_type>::type;template <typename T>using is_unsigned =typename std::conditional<std::is_unsigned<T>::value or is_unsigned_int128<T>::value,std::true_type,std::false_type>::type;template <typename T>using make_unsigned_int128 =typename std::conditional<std::is_same<T, __int128_t>::value, __uint128_t, unsigned __int128>;template <typename T>using to_unsigned =typename std::conditional<is_signed_int128<T>::value,make_unsigned_int128<T>,typename std::conditional<std::is_signed<T>::value,std::make_unsigned<T>,std::common_type<T>>::type>::type;template <typename T> using is_integral_t = std::enable_if_t<is_integral<T>::value>;template <typename T> using is_signed_t = std::enable_if_t<is_signed<T>::value>;template <typename T> using is_unsigned_t = std::enable_if_t<is_unsigned<T>::value>;template <typename T>using is_function_pointer =typename std::conditional<std::is_pointer_v<T> && std::is_function_v<std::remove_pointer_t<T>>,std::true_type,std::false_type>::type;template <typename T, std::enable_if_t<is_function_pointer<T>::value> * = nullptr>struct is_two_args_function_pointer : std::false_type {};template <typename R, typename T1, typename T2>struct is_two_args_function_pointer<R (*)(T1, T2)> : std::true_type {};template <typename T>using is_two_args_function_pointer_t = std::enable_if_t<is_two_args_function_pointer<T>::value>;namespace type_traits {struct istream_tag {};struct ostream_tag {};} // namespace type_traitstemplate <typename T> using is_standard_istream = std::is_same<T, std::istream>;template <typename T> using is_standard_ostream = std::is_same<T, std::ostream>;template <typename T> using is_user_defined_istream = std::is_base_of<type_traits::istream_tag, T>;template <typename T> using is_user_defined_ostream = std::is_base_of<type_traits::ostream_tag, T>;template <typename T>using is_istream =typename std::conditional<is_standard_istream<T>::value || is_user_defined_istream<T>::value,std::true_type,std::false_type>::type;template <typename T>using is_ostream =typename std::conditional<is_standard_ostream<T>::value || is_user_defined_ostream<T>::value,std::true_type,std::false_type>::type;template <typename T> using is_istream_t = std::enable_if_t<is_istream<T>::value>;template <typename T> using is_ostream_t = std::enable_if_t<is_ostream<T>::value>;} // namespace kk2#endif // TYPE_TRAITS_HPP// #include "../type_traits/type_traits.hpp"#ifndef TEMPLATE_FASTIO_HPP#define TEMPLATE_FASTIO_HPP 1#include <cctype>#include <cstdint>#include <cstdio>#include <fstream>#include <iostream>#include <string>// #include "../type_traits/type_traits.hpp"namespace kk2 {namespace fastio {#define INPUT_FILE "in.txt"#define OUTPUT_FILE "out.txt"struct Scanner : type_traits::istream_tag {private:static constexpr size_t INPUT_BUF = 1 << 17;size_t pos = 0, end = 0;static char buf[INPUT_BUF];FILE *fp;public:Scanner() : fp(stdin) {}Scanner(const char *file) : fp(fopen(file, "r")) {}~Scanner() {if (fp != stdin) fclose(fp);}char now() {if (pos == end) {while (!(end = fread(buf, 1, INPUT_BUF, fp))) {}if (end != INPUT_BUF) buf[end] = '\0';pos = 0;}return buf[pos];}void skip_space() {while (isspace(now())) ++pos;}template <class T, is_unsigned_t<T> * = nullptr> T next_unsigned_integral() {skip_space();T res{};while (isdigit(now())) {res = res * 10 + (now() - '0');++pos;}return res;}template <class T, is_signed_t<T> * = nullptr> T next_signed_integral() {skip_space();if (now() == '-') {++pos;return T(-next_unsigned_integral<typename to_unsigned<T>::type>());} else return (T)next_unsigned_integral<typename to_unsigned<T>::type>();}char next_char() {skip_space();auto res = now();++pos;return res;}std::string next_string() {skip_space();std::string res;while (true) {char c = now();if (isspace(c) or c == '\0') break;res.push_back(now());++pos;}return res;}template <class T, is_unsigned_t<T> * = nullptr> Scanner &operator>>(T &x) {x = next_unsigned_integral<T>();return *this;}template <class T, is_signed_t<T> * = nullptr> Scanner &operator>>(T &x) {x = next_signed_integral<T>();return *this;}Scanner &operator>>(char &x) {x = next_char();return *this;}Scanner &operator>>(std::string &x) {x = next_string();return *this;}};struct endl_struct_t {};struct Printer : type_traits::ostream_tag {private:static char helper[10000][5];static char leading_zero[10000][5];constexpr static size_t OUTPUT_BUF = 1 << 17;static char buf[OUTPUT_BUF];size_t pos = 0;FILE *fp;template <class T> static constexpr void div_mod(T &a, T &b, T mod) {a = b / mod;b -= a * mod;}static void init() {buf[0] = '\0';for (size_t i = 0; i < 10000; ++i) {leading_zero[i][0] = i / 1000 + '0';leading_zero[i][1] = i / 100 % 10 + '0';leading_zero[i][2] = i / 10 % 10 + '0';leading_zero[i][3] = i % 10 + '0';leading_zero[i][4] = '\0';size_t j = 0;if (i >= 1000) helper[i][j++] = i / 1000 + '0';if (i >= 100) helper[i][j++] = i / 100 % 10 + '0';if (i >= 10) helper[i][j++] = i / 10 % 10 + '0';helper[i][j++] = i % 10 + '0';helper[i][j] = '\0';}}public:Printer() : fp(stdout) { init(); }Printer(const char *file) : fp(fopen(file, "w")) { init(); }~Printer() {write();if (fp != stdout) fclose(fp);}void write() {fwrite(buf, 1, pos, fp);pos = 0;}void flush() {write();fflush(fp);}void put_char(char c) {if (pos == OUTPUT_BUF) write();buf[pos++] = c;}void put_cstr(const char *s) {while (*s) put_char(*(s++));}void put_u32(uint32_t x) {uint32_t y;if (x >= 100000000) { // 10^8div_mod<uint32_t>(y, x, 100000000);put_cstr(helper[y]);div_mod<uint32_t>(y, x, 10000);put_cstr(leading_zero[y]);put_cstr(leading_zero[x]);} else if (x >= 10000) { // 10^4div_mod<uint32_t>(y, x, 10000);put_cstr(helper[y]);put_cstr(leading_zero[x]);} else put_cstr(helper[x]);}void put_i32(int32_t x) {if (x < 0) {put_char('-');put_u32(-x);} else put_u32(x);}void put_u64(uint64_t x) {uint64_t y;if (x >= 1000000000000ull) { // 10^12div_mod<uint64_t>(y, x, 1000000000000ull);put_u32(y);div_mod<uint64_t>(y, x, 100000000ull);put_cstr(leading_zero[y]);div_mod<uint64_t>(y, x, 10000ull);put_cstr(leading_zero[y]);put_cstr(leading_zero[x]);} else if (x >= 10000ull) { // 10^4div_mod<uint64_t>(y, x, 10000ull);put_u32(y);put_cstr(leading_zero[x]);} else put_cstr(helper[x]);}void put_i64(int64_t x) {if (x < 0) {put_char('-');put_u64(-x);} else put_u64(x);}void put_u128(__uint128_t x) {constexpr static __uint128_t pow10_10 = 10000000000ull;constexpr static __uint128_t pow10_20 = pow10_10 * pow10_10;__uint128_t y;if (x >= pow10_20) { // 10^20div_mod<__uint128_t>(y, x, pow10_20);put_u64(uint64_t(y));div_mod<__uint128_t>(y, x, __uint128_t(10000000000000000ull));put_cstr(leading_zero[y]);div_mod<__uint128_t>(y, x, __uint128_t(1000000000000ull));put_cstr(leading_zero[y]);div_mod<__uint128_t>(y, x, __uint128_t(100000000ull));put_cstr(leading_zero[y]);div_mod<__uint128_t>(y, x, __uint128_t(10000ull));put_cstr(leading_zero[y]);put_cstr(leading_zero[x]);} else if (x >= __uint128_t(10000)) { // 10^4div_mod<__uint128_t>(y, x, __uint128_t(10000));put_u64(uint64_t(y));put_cstr(leading_zero[x]);} else put_cstr(helper[x]);}void put_i128(__int128_t x) {if (x < 0) {put_char('-');put_u128(-x);} else put_u128(x);}template <class T, is_unsigned_t<T> * = nullptr> Printer &operator<<(T x) {if constexpr (sizeof(T) <= 4) put_u32(x);else if constexpr (sizeof(T) <= 8) put_u64(x);else put_u128(x);return *this;}template <class T, is_signed_t<T> * = nullptr> Printer &operator<<(T x) {if constexpr (sizeof(T) <= 4) put_i32(x);else if constexpr (sizeof(T) <= 8) put_i64(x);else put_i128(x);return *this;}Printer &operator<<(char x) {put_char(x);return *this;}Printer &operator<<(const std::string &x) {for (char c : x) put_char(c);return *this;}Printer &operator<<(const char *x) {put_cstr(x);return *this;}// std::cout << std::endl; は関数ポインタを渡しているらしいPrinter &operator<<(endl_struct_t) {put_char('\n');flush();return *this;}};char Scanner::buf[Scanner::INPUT_BUF];char Printer::buf[Printer::OUTPUT_BUF];char Printer::helper[10000][5];char Printer::leading_zero[10000][5];} // namespace fastio#if defined(INTERACTIVE) || defined(USE_STDIO)auto &kin = std::cin;auto &kout = std::cout;auto (*kendl)(std::ostream &) = std::endl<char, std::char_traits<char>>;#elif defined(KK2)fastio::Scanner kin(INPUT_FILE);fastio::Printer kout(OUTPUT_FILE);fastio::endl_struct_t kendl;#elsefastio::Scanner kin;fastio::Printer kout;fastio::endl_struct_t kendl;#endif} // namespace kk2#endif // TEMPLATE_FASTIO_HPP// #include "fastio.hpp"using u32 = unsigned int;using i64 = long long;using u64 = unsigned long long;using i128 = __int128_t;using u128 = __uint128_t;using pi = std::pair<int, int>;using pl = std::pair<i64, i64>;using pil = std::pair<int, i64>;using pli = std::pair<i64, int>;template <class T> using vc = std::vector<T>;template <class T> using vvc = std::vector<vc<T>>;template <class T> using vvvc = std::vector<vvc<T>>;template <class T> using vvvvc = std::vector<vvvc<T>>;template <class T> using pq = std::priority_queue<T>;template <class T> using pqi = std::priority_queue<T, std::vector<T>, std::greater<T>>;template <class T> constexpr T infty = 0;template <> constexpr int infty<int> = (1 << 30) - 123;template <> constexpr i64 infty<i64> = (1ll << 62) - (1ll << 31);template <> constexpr i128 infty<i128> = (i128(1) << 126) - (i128(1) << 63);template <> constexpr u32 infty<u32> = infty<int>;template <> constexpr u64 infty<u64> = infty<i64>;template <> constexpr u128 infty<u128> = infty<i128>;template <> constexpr double infty<double> = infty<i64>;template <> constexpr long double infty<long double> = infty<i64>;constexpr int mod = 998244353;constexpr int modu = 1e9 + 7;constexpr long double PI = 3.14159265358979323846;namespace kk2 {template <class T, class... Sizes> auto make_vector(int first, Sizes... sizes) {if constexpr (sizeof...(sizes) == 0) {return std::vector<T>(first);} else {return std::vector<decltype(make_vector<T>(sizes...))>(first, make_vector<T>(sizes...));}}template <class T, class U> void fill_all(std::vector<T> &v, const U &x) {std::fill(std::begin(v), std::end(v), T(x));}template <class T, class U> void fill_all(std::vector<std::vector<T>> &v, const U &x) {for (auto &u : v) fill_all(u, x);}} // namespace kk2template <class T, class S> inline bool chmax(T &a, const S &b) {return (a < b ? a = b, 1 : 0);}template <class T, class S> inline bool chmin(T &a, const S &b) {return (a > b ? a = b, 1 : 0);}#define rep1(a) for (i64 _ = 0; _ < (i64)(a); ++_)#define rep2(i, a) for (i64 i = 0; i < (i64)(a); ++i)#define rep3(i, a, b) for (i64 i = (a); i < (i64)(b); ++i)#define repi2(i, a) for (i64 i = (a) - 1; i >= 0; --i)#define repi3(i, a, b) for (i64 i = (a) - 1; i >= (i64)(b); --i)#define overload3(a, b, c, d, ...) d#define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)#define repi(...) overload3(__VA_ARGS__, repi3, repi2, rep1)(__VA_ARGS__)#define fi first#define se second#define all(p) std::begin(p), std::end(p)using kk2::kendl;using kk2::kin;using kk2::kout;struct IoSetUp {IoSetUp() {std::cin.tie(nullptr);std::ios::sync_with_stdio(false);}} iosetup;template <class OStream, class T, class U, kk2::is_ostream_t<OStream> * = nullptr>OStream &operator<<(OStream &os, const std::pair<T, U> &p) {os << p.first << ' ' << p.second;return os;}template <class IStream, class T, class U, kk2::is_istream_t<IStream> * = nullptr>IStream &operator>>(IStream &is, std::pair<T, U> &p) {is >> p.first >> p.second;return is;}template <class OStream, class T, kk2::is_ostream_t<OStream> * = nullptr>OStream &operator<<(OStream &os, const std::vector<T> &v) {for (int i = 0; i < (int)v.size(); i++) { os << v[i] << (i + 1 == (int)v.size() ? "" : " "); }return os;}template <class IStream, class T, kk2::is_istream_t<IStream> * = nullptr>IStream &operator>>(IStream &is, std::vector<T> &v) {for (auto &x : v) is >> x;return is;}void Yes(bool b = 1) {kout << (b ? "Yes\n" : "No\n");}void No(bool b = 1) {kout << (b ? "No\n" : "Yes\n");}void YES(bool b = 1) {kout << (b ? "YES\n" : "NO\n");}void NO(bool b = 1) {kout << (b ? "NO\n" : "YES\n");}void yes(bool b = 1) {kout << (b ? "yes\n" : "no\n");}void no(bool b = 1) {kout << (b ? "no\n" : "yes\n");}#endif // TEMPLATE// #include <kk2/template/template.hpp>using namespace std;void solve() {int d, x, y;kin >> d >> x >> y;if (x == 0) {kout << 1ll * y * d << kendl;return;}if (y == 0) {kout << 1ll * x * d << kendl;return;}int g = gcd(x, y);int s = x / g, t = y / g;int mn_k = max(kk2::fracceil(-x, t), kk2::fracceil(y - d, s));int mx_k = min(kk2::fracfloor(d - x, t), kk2::fracfloor(y, s));// kout << mn_k << ' ' << mx_k << kendl;i64 res = 0;{int x1 = mn_k * t + x;int y1 = -mn_k * s + y;chmax(res, abs(1ll * x * y1 - 1ll * y * x1));}{int x1 = mx_k * t + x;int y1 = -mx_k * s + y;chmax(res, abs(1ll * x * y1 - 1ll * y * x1));}kout << res << kendl;}int main() {int t = 1;kin >> t;rep (t) solve();return 0;}// converted!!