#712882 (C++17) No.210 探し物はどこですか？

• 問題: No.210 探し物はどこですか？
• ユーザー: 沙耶花
• 提出日時: 2021-11-04 21:08:53
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 1,156 bytes
• コンパイル時間: 4,263 ms
• コンパイル使用メモリ: 261,996 KB
• 実行使用メモリ: 6,948 KB
• 最終ジャッジ日時: 2024-04-23 04:00:38
• 合計ジャッジ時間: 11,619 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	71 ms; 6,816 KB
testcase_01	AC	106 ms; 6,940 KB
testcase_02	WA	-
testcase_03	RE	-
testcase_04	RE	-
testcase_05	RE	-
testcase_06	AC	393 ms; 6,940 KB
testcase_07	AC	360 ms; 6,944 KB
testcase_08	AC	40 ms; 6,940 KB
testcase_09	RE	-
testcase_10	AC	38 ms; 6,940 KB
testcase_11	RE	-
testcase_12	RE	-
testcase_13	AC	68 ms; 6,940 KB
testcase_14	RE	-
testcase_15	AC	210 ms; 6,940 KB
testcase_16	AC	210 ms; 6,940 KB
testcase_17	AC	327 ms; 6,944 KB
testcase_18	AC	71 ms; 6,944 KB
testcase_19	RE	-
testcase_20	RE	-
testcase_21	RE	-
testcase_22	AC	73 ms; 6,940 KB
testcase_23	RE	-
testcase_24	RE	-
testcase_25	RE	-
testcase_26	AC	102 ms; 6,940 KB
testcase_27	RE	-
testcase_28	AC	106 ms; 6,940 KB
testcase_29	AC	105 ms; 6,944 KB
testcase_30	AC	112 ms; 6,944 KB
testcase_31	AC	109 ms; 6,944 KB
testcase_32	AC	106 ms; 6,940 KB
testcase_33	RE	-
testcase_34	AC	113 ms; 6,944 KB
testcase_35	RE	-
testcase_36	AC	113 ms; 6,944 KB
testcase_37	RE	-
testcase_38	AC	115 ms; 6,940 KB
testcase_39	AC	111 ms; 6,944 KB
testcase_40	AC	112 ms; 6,940 KB
testcase_41	AC	116 ms; 6,940 KB
testcase_42	AC	114 ms; 6,944 KB
testcase_43	AC	9 ms; 6,944 KB
testcase_44	AC	39 ms; 6,940 KB
testcase_45	AC	349 ms; 6,940 KB

ソースコード

#include <stdio.h>
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using mint = modint1000000007;
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf 1000000000000000
using P = pair<double,int>;
P op(P a,P b){
	return max(a,b);
}
P e(){
	return make_pair(0.0,-1);
}

P mapping(double a,P b){
	b.first *= a;
	return b;
}

double composition(double a,double b){
	return a*b;
}

double id(){
	return 1.0;
}

int main(){	
	
	int n;
	cin>>n;
	
	vector<double> p(n),q(n);
	rep(i,n){
		cin>>p[i];
		p[i] /= 1000.0;
	}
	rep(i,n){
		cin>>q[i];
		q[i] /= 100.0;
	}	
	
	double ans = 0.0;
	double pp = 1.0;
	
	vector<P> temp(n);
	rep(i,n)temp[i] = make_pair(p[i]*q[i],i);
	
	lazy_segtree<P,op,e,double,mapping,composition,id> seg(temp);

	rep(_,450000){
		ans += pp;
		P r = seg.all_prod();
	//	if(_<10)cout<<r.first<<','<<r.second<<endl;
		pp *= 1.0 - r.first;
		double ps = 1.0;
		r.first /= q[r.second];
		ps -= r.first;
		r.first *= 1.0 - q[r.second];
		ps += r.first;
		r.first *= q[r.second];
		seg.set(r.second,r);
		
		seg.apply(0,n,1.0 / ps);
	}
	
	cout<<fixed<<setprecision(10)<<ans<<endl;

	return 0;
	
}