結果

問題 No.691 E869120 and Constructing Array 5
ユーザー Guowen Rong
提出日時 2025-09-27 12:17:30
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,227 bytes
コンパイル時間 2,412 ms
コンパイル使用メモリ 214,396 KB
実行使用メモリ 20,220 KB
最終ジャッジ日時 2025-09-27 12:17:38
合計ジャッジ時間 7,320 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other TLE * 1 -- * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void solve()’:
main.cpp:84:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   84 |         scanf("%Lf", &p);
      |         ~~~~~^~~~~~~~~~~

ソースコード

diff # 

 #include<bits/stdc++.h>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define add(x, y) ((x + y >= mod) ? (x + y - mod) : (x + y))
#define dec(x, y) ((x - y < 0) ? (x - y + mod) : (x - y))
#define popcnt(x) __builtin_popcount(x)
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef long double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
	if(x < 0){
		putchar('-');
		x = -x;
	}
	if(x > 9)
	  write(x / 10);
	putchar(x % 10 + '0');
}
mt19937 R(time(0));
int q;
db p;
inline db get(vector<ll> A){
    db ans = 0;
    for(auto v : A)
      ans += sqrt(v);
    return ans;
}
inline vector<ll> get(db X){
	db eps = 5e-5;
	vector<pair<db, vector<ll>>> T1, T2;
	db T = X / 8.0;
	while(T1.size() < 100){
//		cerr << x << '\n';
		// sqrt a + sqrt b - T <= eps
		ll a = R() % ((ll)(T * T));
		db sb = T - sqrt(a);
		for(int i = 0; i <= 1; ++i)
		  if(fabs(sqrt(a) + sqrt((ll)(sb * sb) + i) - T) < 5e-5)
		    T1.push_back({sqrt(a) + sqrt((ll)(sb * sb) + i), {a, (ll)(sb * sb) + i}});
	}
	for(int cas = 1; cas <= 3; ++cas){
		eps *= 1e-2;
		T *= 2;
		T2.clear();
		for(auto x : T1){
			for(auto y : T1){
				if(fabs(x.fi + y.fi - T) <= eps){
					pair<db, vector<ll>> t = {x.fi + y.fi, x.se};
					for(auto v : y.se)
					  t.se.push_back(v);
					T2.push_back(t); 
				}
			}
		}
		T1 = T2;
	}
	if(T1.empty())
	  return {};
	return T1[0].se;
}
inline void solve(){
	vector<ll> ans;
	scanf("%Lf", &p);
	while(1){
		ans = get(p);
		if(ans.size())
		  break;
	}
	write(ans.size());
	putchar(' ');
	for(auto v : ans){
		write(v);
		putchar(' ');
	}
	putchar('\n');
//	printf("%.10Lf\n", get(ans));
}
bool End;
int main(){
//	open("squareroot.in", "squareroot.out");
	q = read();
	while(q--)
	  solve();
	//cerr << '\n' << abs(&Begin - &End) / 1048576 << "MB";
	return 0;
}
0