#885963 (C++17) No.2368 I love a square root of 2

提出ソース

結果

問題	No.2368 I love a square root of 2
ユーザー	Hoget157
提出日時	2023-06-30 22:04:32
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	270 ms / 2,000 ms
コード長	7,840 bytes
コンパイル時間	3,125 ms
コンパイル使用メモリ	246,028 KB
実行使用メモリ	4,380 KB
最終ジャッジ日時	2023-09-21 16:05:39
合計ジャッジ時間	6,871 ms
ジャッジサーバーID （参考情報）	judge12 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	59 ms 4,376 KB
testcase_01	AC	59 ms 4,376 KB
testcase_02	AC	268 ms 4,376 KB
testcase_03	AC	59 ms 4,380 KB
testcase_04	AC	59 ms 4,376 KB
testcase_05	AC	60 ms 4,380 KB
testcase_06	AC	60 ms 4,376 KB
testcase_07	AC	60 ms 4,380 KB
testcase_08	AC	60 ms 4,380 KB
testcase_09	AC	59 ms 4,376 KB
testcase_10	AC	59 ms 4,380 KB
testcase_11	AC	59 ms 4,380 KB
testcase_12	AC	59 ms 4,376 KB
testcase_13	AC	228 ms 4,376 KB
testcase_14	AC	230 ms 4,376 KB
testcase_15	AC	248 ms 4,380 KB
testcase_16	AC	184 ms 4,376 KB
testcase_17	AC	61 ms 4,380 KB
testcase_18	AC	64 ms 4,380 KB
testcase_19	AC	65 ms 4,380 KB
testcase_20	AC	64 ms 4,376 KB
testcase_21	AC	270 ms 4,376 KB
testcase_22	AC	261 ms 4,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#pragma region header
// #pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
// #include <atcoder/all>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define isIn(x, y, h, w) ((x) >= 0 && (x) < (h) && (y) >= 0 && (y) < (w))
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(auto i = (n) - 1; i >= 0; i--)
#define repi(i, n1, n2) for(auto i = (n1); i < (n2); i++)
#define rrepi(i, n1, n2) for(auto i = (n2) - 1; i >= (n1); i--)
#define rep2(i, j, n) rep(i, n) repi(j, i + 1, n)
#define DFS(...) self(self, __VA_ARGS__)
#define min_equal(v, x) lower_bound(all(v), (x)) - (v).begin()
#define min_over(v, x) upper_bound(all(v), (x)) - (v).begin()
#define max_equal(v, x) upper_bound(all(v), (x)) - (v).begin() - 1
#define max_under(v, x) lower_bound(all(v), (x)) - (v).begin() - 1

template<class T, class U> static inline vector<U> makevec(const T &n, const U &u){ return vector<U>(n, u); }
template<class T, class... Args> static inline auto makevec(const T &n, const Args&... args){ return vector<decltype(makevec(args...))>(n, makevec(args...)); }

#define in(T, ...) T __VA_ARGS__; input(__VA_ARGS__)
#define inrows(n, ...) rep(inrows_, n) inrow(__VA_ARGS__)
#define invec(T, n, ...) vector<T> __VA_ARGS__; inputvec(n, __VA_ARGS__);
#define invec2(T, n, m, x) vector<vector<T>> x(n, vector<T>(m)); input(x)
template<class... T> inline void input(T&... x){ (cin >> ... >> x); }
template<class T> inline void inputvec(const T &n){ (void)n; }
template<class T, class Head, class... Tail> inline void inputvec(const T &n, Head &v, Tail&... tail){ v.resize(n); cin >> v; inputvec(n, tail...); }
inline void inrow(){}
template<class Head, class... Tail> inline void inrow(Head &x, Tail&... tail){ in(typename Head::value_type, y); x.push_back(y); inrow(tail...); }
template<class T> istream &operator>>(istream &is, vector<T> &x){ for(auto &&v : x) is >> v; return is; }
#define INT(...) in(int, __VA_ARGS__)
#define STR(...) in(string, __VA_ARGS__)
#define CHAR(...) in(char, __VA_ARGS__)
#define VI(n, ...) invec(int, (n), __VA_ARGS__)
#define VS(n, ...) invec(string, (n), __VA_ARGS__)

#ifdef DEBUG
#define dbg(...) cout << #__VA_ARGS__ << ": "; print(__VA_ARGS__); cout << flush
#else
#define dbg(...) (static_cast<void>(0))
#endif
const string DELIMITER[] = 
#ifdef DEBUG 
	{",", "(", ")", "[", "]"};
#else
	{" ", "", "", "", ""};
#endif
ostream &operator<<(ostream &os, __int128_t x){
	if(x < 0) x *= -1, os << '-';
	vector<int> v;
	while(x) v.push_back(x % 10), x /= 10;
	if(!v.size()) return os << 0;
	for(int i = (int)v.size() - 1; i >= 0; i--) os << v[i];
	return os;
}
// template<auto T> ostream &operator<<(ostream &os, const atcoder::static_modint<T> &x){ return os << x.val(); }
// template<auto T> ostream &operator<<(ostream &os, const atcoder::dynamic_modint<T> &x){ return os << x.val(); }
template<class T, class U> ostream &operator<<(ostream &os, const pair<T, U> &p){ return os << DELIMITER[1] << p.first << DELIMITER[0] << p.second << DELIMITER[2]; }
template<typename T, typename U = typename T::iterator, enable_if_t<!is_same_v<T, string> && !is_same_v<T, wstring>, nullptr_t> = nullptr>
ostream &operator<<(ostream &os, const T &c){
	for(auto it = c.begin(); it != c.end(); it++) os << DELIMITER[(it == c.begin()) ? 3 : 0] << *it;
	return os << DELIMITER[4];
}
template<class T> inline void prend(const T &a){ cout << a << '\n'; exit(0); }
template<class T> inline void print(const T &a){ cout << a << '\n'; }
template<class Head, class... Tail> inline void print(const Head &a, const Tail&... b){ cout << a << ' '; print(b...); }
inline void prec(const int d){ cout << fixed << setprecision(d); }

const vector<vector<string>> YN_string = {{"Yes", "No"}, {"YES", "NO"}, {"Takahashi", "Aoki"}, {"Alice", "Bob"}, {"Possible", "Impossible"}};
enum class YesNo{ Yes, YES, taka, alice, poss };

inline void i0(){}
template<class T, enable_if_t<is_integral_v<T>, nullptr_t> = nullptr, class... Tail> inline void i0(T &x, Tail&... tail){ x--; i0(tail...); }
template<class T, class... Tail> inline void i0(vector<T> &v, Tail&... tail){ for(auto &&x : v) i0(x); i0(tail...); }

template<class T> inline T div_floor(T a, T b){ if(b < 0) a = -a, b = -b; return a >= 0 ? a / b : (a + 1) / b - 1; }
template<class T> inline T div_ceil(T a, T b){ if(b < 0) a = -a, b = -b; return a <= 0 ? a / b : (a - 1) / b + 1; }
template<class T> inline T div_less(T a, T b){ return div_floor(a, b) - !(a % b); }
template<class T> inline T div_greater(T a, T b){ return div_ceil(a, b) + !(a % b); }

template<class T> inline void sort(vector<T> &v){ sort(v.begin(), v.end()); }
template<class T> inline void rsort(vector<T> &v){ sort(v.rbegin(), v.rend()); }
template<class T> inline void unique(vector<T> &v){ sort(v); v.erase(unique(v.begin(), v.end()), v.end()); }
template<class T> inline auto min(const T &a){ return *min_element(a.begin(), a.end()); }
template<class T> inline auto max(const T &a){ return *max_element(a.begin(), a.end()); }
template<class T> inline bool chmin(T &a, const T &b){ return a > b ? a = b, true : false; }
template<class T> inline bool chmax(T &a, const T &b){ return a < b ? a = b, true : false; }
template<class T> inline typename T::value_type mex(const T &st){ for(auto i = typename T::value_type(0); ; i++) if(!st.count(i)) return i; }
template<class T> inline T calc_sum(const vector<T> &v){ return accumulate(v.begin(), v.end(), T(0)); }

using ld = long double;
using ll = long long;
using l128 = __int128;
template<class T> using P = pair<T, T>;
template<class T> using tup3 = tuple<T, T, T>;
template<class T> using heap = priority_queue<T, vector<T>, greater<T>>;
template<class T> using vec2 = vector<vector<T>>;
template<class T> using vec3 = vector<vec2<T>>;
template<class T> using uset = unordered_set<T>;
template<class T, class U> using umap = unordered_map<T, U>;

struct FastIO{ FastIO(){ cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); prec(10); } } fastio__;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
template<class T> using tree = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;

#pragma endregion header

#define int long long
const int inf = 2e9;
const int INF = 2e18;
const double EPS = 1e-8;
const int MOD = 998244353;
using pi = pair<int, int>;
using ipi = pair<int, pair<int, int>>;
using pii = pair<pair<int, int>, int>;
using vi = vector<int>;
using vpi = vector<pi>;
using vs = vector<string>;
using vd = vector<double>;
using vvi = vector<vector<int>>;
// using mint = atcoder::modint1000000007;
// using mint = atcoder::modint998244353;
// using mint = atcoder::modint;
// using vm = vector<mint>;
const int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
#define YN YesNo::Yes
inline void Yes(bool end = false){ print(YN_string[(int)YN][0]); if(end) exit(0); }
inline void No(bool end = false){ print(YN_string[(int)YN][1]); if(end) exit(0); }
inline void isYes(bool x, bool end = false){ print(YN_string[(int)YN][!x]); if(end) exit(0); }

template<class T, class F>
T bsearch(T ok, T ng, const F &check, const int max_loop = -1){
	for(int i = 0; (max_loop == -1) ? (abs(ok - ng) > 1) : (i < max_loop); i++){
		T mid = (ok + ng) / 2;
		(check(mid) ? ok : ng) = mid;
	}
	return ok;
}

signed main(){
	const int MAX = 200000;
	in(int, n);
	auto check = [&](ld x){
		int sum = 0;
		rep(i, MAX){
			if(x < i) continue;
			sum += max(0ll, (int)((x - i) / sqrt(2)) + 1);
		}
		if(x < 10) dbg(x, sum);
		return sum < n;
	};
	ld x = bsearch(ld(0), (ld)MAX, check, 300);
	dbg(x);
	int p, q;
	rep(i, MAX){
		ld b2 = (x - i) / sqrt(2);
		if(b2 > -EPS && abs(round(b2) - b2) < EPS){
			print(i, (int)round(b2));
			return 0;
		}
	}
}

yukicoder

結果

テストケース

ソースコード