結果
| 問題 |
No.691 E869120 and Constructing Array 5
|
| コンテスト | |
| ユーザー |
|
| 提出日時 | 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);
| ~~~~~^~~~~~~~~~~
ソースコード
#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;
}