結果
| 問題 | No.691 E869120 and Constructing Array 5 |
| ユーザー |
 WA_TLE
|
| 提出日時 | 2018-05-07 00:40:27 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 4,582 bytes |
| コンパイル時間 | 2,066 ms |
| コンパイル使用メモリ | 156,848 KB |
| 実行使用メモリ | 5,376 KB |
| 最終ジャッジ日時 | 2024-06-28 13:33:16 |
| 合計ジャッジ時間 | 6,835 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 21 ms
5,248 KB |
| testcase_01 | AC | 21 ms
5,376 KB |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | AC | 16 ms
5,376 KB |
ソースコード
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
//cout<<setprecision(20)
//cin.tie(0);
//ios::sync_with_stdio(false);
const llint mod=1000000007;
const llint big=4.19e18+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>int LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>int UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
int main(void){
int Q,i;cin>>Q;
int Tsize=10000;
cerr<<setprecision(20);
//結構いける
vector<pair<lldo,array<int,12>>>Stable;
//4000 .12.5桁調整表(12つの数字)4000±3*10^-10までがT個
vector<pair<lldo,array<int,6>>>Mtable;
//2000 .9 桁調整表(6つの数字)2000±10^-6までがT個
vector<pair<lldo,array<int,3>>>Ltable;
//1000 .5.5 桁調整表(3つの数字)1000±3*10^-3までがT個
//各テーブルは、一つ下から作られる
//それに加えて,最初の3つがランダム 1つが±10^-3
//合計25個 かなり余裕
//Ltable作る
Ltable.reserve(Tsize);
mt19937 engine(1333);
lldo epL=0.003;
lldo epM=0.000003;
lldo epS=0.000000003;
lldo epSS=eps/3000;
//各段階で1000倍 余裕でしょう
while(Ltable.size()<Tsize){
int La=engine()%(500*500);
int Lbm=((800-sqrt(La))*(800-sqrt(La)));
int Lb=engine()%Lbm;
int Lcmin=1+(1000-epL-sqrt(La)-sqrt(Lb))*(1000-epL-sqrt(La)-sqrt(Lb));
int Lcmax=(1000+epL-sqrt(La)-sqrt(Lb))*(1000+epL-sqrt(La)-sqrt(Lb));
//±3*10^-3に入るものをランダムに選ばないといけない
//scmin以上scmax
if(Lcmin>Lcmax){continue;}
//cerr<<"Lhab="<<Lcmax-Lcmin+1<<" ";
int raL=engine()%(Lcmax+1-Lcmin);
int Lc=Lcmin+raL;
lldo Lans=sqrt(La)+sqrt(Lb)+sqrt(Lc);
array<int,3>Lsor;
Lsor[0]=La;Lsor[1]=Lb;Lsor[2]=Lc;
Ltable.pub(mp(Lans,Lsor));
//cerr<<"ans="<<abs(1000-Lans)<<endl;
}
//cerr<<"de";
SO(Ltable);
//cerr<<"de";
//Mtable作る
Mtable.reserve(Tsize);
array<int,3>Mkara;
while(Mtable.size()<Tsize){
int Mter=engine()%Tsize;
int Mcmin=LBI(Ltable,mp(2000-epM-Ltable[Mter].fir,Mkara));
int Mcmax=LBI(Ltable,mp(2000+epM-Ltable[Mter].fir,Mkara))-1;
if(Mcmin>Mcmax){continue;}
int raM=engine()%(Mcmax+1-Mcmin);
int Mc=Mcmin+raM;
lldo Mans=Ltable[Mter].fir+Ltable[Mc].fir;
array<int,6>Msor;
for(i=0;i<3;i++){Msor[i]=Ltable[Mter].sec[i];}
for(i=0;i<3;i++){Msor[i+3]=Ltable[Mc].sec[i];}
Mtable.pub(mp(Mans,Msor));
//if(Mtable.size()<100){cerr<<"ans="<<abs(2000-Mans)<<endl;}
}
SO(Mtable);
array<int,6>Skara;
array<int,12>SSkara;
while(Stable.size()<Tsize){
int Ster=engine()%Tsize;
int Scmin=LBI(Mtable,mp(4000-epS-Mtable[Ster].fir,Skara));
int Scmax=LBI(Mtable,mp(4000+epS-Mtable[Ster].fir,Skara))-1;
if(Scmin>Scmax){continue;}
int raS=engine()%(Scmax+1-Scmin);
int Sc=Scmin+raS;
lldo Sans=Mtable[Ster].fir+Mtable[Sc].fir;
array<int,12>Ssor;
for(i=0;i<6;i++){Ssor[i]=Mtable[Ster].sec[i];}
for(i=0;i<6;i++){Ssor[i+6]=Mtable[Sc].sec[i];}
Stable.pub(mp(Sans,Ssor));
//if(Stable.size()<100){cerr<<"ans="<<abs(4000-Sans)<<endl;}
}
SO(Stable);
while(Q--){
//最初は適当でよい
lldo P;cin>>P;
cout<<22<<" ";//22個使う
int hazi=(P-7000)*(P-7000) +0.5;
P-=sqrt(hazi);
cout<<hazi<<" ";
auto Lban=LBI(Ltable,mp(P-6000,Mkara));
for(i=0;i<3;i++){cout<<Ltable[Lban].sec[i]<<" ";}
P-=Ltable[Lban].fir;
auto Mban=LBI(Mtable,mp(P-4000,Skara));
for(i=0;i<6;i++){cout<<Mtable[Mban].sec[i]<<" ";}
P-=Mtable[Mban].fir;
auto Sban=LBI(Stable,mp(P,SSkara));
for(i=0;i<12;i++){cout<<Stable[Sban].sec[i]<<" ";}
P-=Stable[Sban].fir;
//cerr<<abs(P)<<endl;
}
return 0;
}