結果

問題 No.691 E869120 and Constructing Array 5
コンテスト
ユーザー vjudge1
提出日時 2025-09-22 12:45:01
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,779 bytes
コンパイル時間 1,689 ms
コンパイル使用メモリ 174,720 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-09-22 12:45:28
合計ジャッジ時間 24,617 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 25 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0