結果
問題 |
No.691 E869120 and Constructing Array 5
|
ユーザー |
|
提出日時 | 2025-09-22 12:45:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,779 bytes |
コンパイル時間 | 1,899 ms |
コンパイル使用メモリ | 208,120 KB |
実行使用メモリ | 7,720 KB |
最終ジャッジ日時 | 2025-09-22 12:46:26 |
合計ジャッジ時間 | 25,264 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 1 |
other | WA * 25 TLE * 2 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll=long long; /* 1e-1->s(26)=5.09901951359278483002 1e-2->2s(2)+3s(13)+5s(15)=33.009997682175242402857368 1e-3->3s(2)+s(11)+4s(83)=44.00099979405188052330 1e-4->5s(2)+3s(11)+5s(23)=41.0000997994952 1e-5->s(2)+s(15)+16s(3)=33.00000982968254863 1e-6->5s(18)+4s(26)+2s(94)=61.0000009196328 1e-7->??? */ const double lim[5]={0,0,1e-6,1e-8,1.1e-10}; int q; double x; vector<vector<int>> v[5]; vector<double> ns[5]; mt19937 mt(time(0)); int rd(int lim){ return mt()%lim+1; } bool ch(){ for(int i=1;i<5;++i){ v[i].clear(); ns[i].clear(); } int T=200; while(T--){ const int lm=x/8*x/8; int no=rd(lm); int ts=(x/8-sqrt(no))*(x/8-sqrt(no)); v[1].emplace_back(); v[1].back().push_back(no); v[1].back().push_back(ts); ns[1].push_back(sqrt(no)+sqrt(ts)); v[1].emplace_back(); v[1].back().push_back(no); v[1].back().push_back(ts+1); ns[1].push_back(sqrt(no)+sqrt(ts+1)); } for(int i=2;i<=4;++i){ const double s=x/(1<<(4-i)); int si=v[i-1].size(); for(int j=0;j<si;++j){ for(int k=j+1;k<si;++k){ if(fabs(s-ns[i-1][j]-ns[i-1][k])<=lim[i]){ ns[i].push_back(ns[i-1][j]+ns[i-1][k]); v[i].push_back(v[i-1][j]); for(int val:v[i-1][k]){ v[i].back().push_back(val); } } } } } return ns[4].size()>0; } int main(){ cin>>q; while(q--){ cin>>x; while(!ch()); cout<<v[4][0].size()<<' '; for(int x:v[4][0]){ cout<<x<<' '; } cout<<'\n'; } return 0; }