結果

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

ソースコード

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 long double lim[5]={0,5e-5,5e-7,5e-9,1.1e-10};
int q;
long double x;
vector<vector<int>> v[5];
vector<long 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();
    }
    while(v[1].size()<100){
        const int lm=x/8*x/8;
        int no=rd(lm);
        int ts=(x/8-sqrtl(no))*(x/8-sqrtl(no));
        long double sum=sqrtl(no)+sqrtl(ts);
        if(fabsl(sum-x/8)<lim[1]){
            v[1].emplace_back();
            v[1].back().push_back(no);
            v[1].back().push_back(ts);
            ns[1].push_back(sum);
        }
        sum=sqrtl(no)+sqrtl(ts+1);
        if(fabsl(sum-x/8)<lim[1]){
            v[1].emplace_back();
            v[1].back().push_back(no);
            v[1].back().push_back(ts+1);
            ns[1].push_back(sum);
        }
    }
    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(fabsl(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(){
    //freopen("squareroot.in","r",stdin);
    //freopen("squareroot.out","w",stdout);
    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