Submission #39886265

---

Source Code Expand

#pragma GCC optimize ("O3")

#include <bits/stdc++.h>
using namespace std;

using ll = long long; 
using ld = long double; 
using str = string; 

using pii = pair<int, int>; 
using pll = pair<ll, ll>; 
#define MP make_pair
#define fs first 
#define sc second

using ull = unsigned long long; 
using mii = map<int, int>; 
using mll = map<ll, ll>; 
#define fd(x, e) (x.find(e) != x.end())

#define tcT template <class T
#define tcTU tcT, class U
#define vt vector //tcT > using vt = vector<T>;
#define ar array // tcT, size_t SZ > using ar = array<T, SZ>;
using vi = vt<int>;
using vb = vt<bool>;
using vl = vt<ll>;
using vd = vt<ld>;
using vs = vt<str>;
using vii = vt<pii>;
using vll = vt<pll>;

#define sz(x) int((x).size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sor(x) sort(x.begin(), x.end()) 
#define rsz resize
#define ins insert
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk back()

#define ts to_string

#define ub upper_bound
#define lb lower_bound
tcT> int lwb(vt<T> &a, const T &b) { return int(lb(all(a), b) - bg(a)); }
tcT> int upb(vt<T> &a, const T &b) { return int(ub(all(a), b) - bg(a)); }

#define rp(i, e) for (int (i) = 0; (i) < (int) (e); (i)+=1)
#define rp2(i, a, e) for (int (i) = (a); (i) < (int) (e); (i)+=1)
#define rp3(i, a, e, s) for (int (i) = (a); (i) < (int) (e); (i)+=(s))
#define	rpr(i, e) for (int (i) = (e) - 1; i > -1; (i)-=1)
#define rp4(i, a, e) for (int (i) = a; (i) > (int) (e); (i)-=1)
#define rp5(i, a, e, s) for (int (i) = a; (i) > (int) (e); (i)+=(s))
#define E(a, x) for (auto &a: x) 

#define nr(a, n) rp(i, n) {cin >> (a)[i];}
#define nr2(a, n, m) rp(i, n)  rp(j, m) cin >> (a)[i][j]; 
#define quick ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)

const ld PI = acos((ld)-1);
const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1}; // for every grid problem!!
tcT> using pqg = priority_queue<T, vector<T>, greater<T>>;

constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set
constexpr ll pctll(ll x) { return __builtin_popcountll(x); } 
constexpr int bits(
	int x) { // assert(x >= 0); 
	return x == 0 ? 0 : 31 - __builtin_clz(x);
} // floor(log2(x))
// constexpr int p2(int x) { return 1 << x; }
// constexpr int msk2(int x) { return p2(x) - 1; }

// ------ ------ ------ IO ------ ------ ------ //
template <class A> void re(vt<A>& v);
template <class A, size_t S> void re(array<A, S>& a);

tcT> void re(T& x) { 
	cin >> x;
}
void re(double& d) { 
	string t; 
	re(t); 
	d=stod(t); 
}
void re(long double& d) { 
	string t; 
	re(t); 
	d=stold(t); 
}
tcT> void re(pair<T, T> & p) { 
	T a, b; 
	re(a); 
	re(b); 
	p=make_pair(a, b); 
}
template<class H, class... T> void re(H& h, T&... t) {
	re(h); 
	re(t...); 
}
template<class A> void re(vt<A>& x) { 
	for (auto &a: x) re(a); 
}
template<class A, size_t S> void re(array<A, S>& x) { 
	for (auto &a: x) re(a); 
}
string to_string(char c) { 
	return string(1, c); 
}
string to_string(bool b) { 
	return b?"YES":"NO";
}
string to_string(const char* s) { 
	return string(s); }
string to_string(string s) { 
	return s; 
}
string to_string(vt<bool> v) { 
	string res; 
	rp(i, sz(v)) 
		res+=char('0'+v[i]);  
	return res; 
}
template<size_t S> string to_string(bitset<S> b) { 
	string res; 
	rp(i, S)
		res+=char('0'+b[i]);
	return res; 
}
tcT> string to_string(pair<T, T> p) { 
	string res;
	res += to_string(p.first); 
	res += ' '; 
	res += to_string(p.second); 
	return res;
}
tcT> string to_string(vt<T> & v) { 
	bool f=1; 
	string res; 
	for (auto& x: v) { 
		if(!f) 
			res+=' ';
		f=0; 
		res+=to_string(x);
	} 
	return res;
}
template<class A> void write(A x) { 
	cout << to_string(x); 
}
template<class H, class... T> void write(const H& h, const T&... t) { 
	write(h); 
	write(t...); 
}
void print() { 
	write("\n");
}
template<class H, class... T> void print(const H& h, const T&... t) { 
	write(h); 
	if(sizeof...(t)) 
		write(' '); 
	print(t...);
}
void DBG() {
	cerr << "]" << endl;
}
template<class H, class... T> void DBG(H h, T... t) {
	cerr << to_string(h);
	if(sizeof...(t))
		cerr << ", ";
	DBG(t...);
}
#define wr write
#define ps print
// ------ ------ ------ alg ------ ------ ------ //
tcTU> void sort(vt<T> & a, U f) { 
	sort(a.begin(), a.end(), f); 
}
tcT> void rsor(vt<T> & a) { 
	sort(a.begin(), a.end(), greater<T>()); 
}
void rsor(str & a) { 
	sort(a.begin(), a.end(), greater<char>()); 
}
tcT> void rev(vt<T> & a){ 
	reverse(a.begin(), a.end()); 
}
void rev(str & a){ 
	reverse(a.begin(), a.end()); 
}

#define vmax(x) *max_element(begin(x), end(x))
#define vmin(x) *min_element(begin(x), end(x))
#define umax(x, n) *max_element((x), (x) + (n))
#define umin(x, n) *min_element((x), (x) + (n))

tcT> bool amin(T & a, const T & b) {
	return b<a?a=b, 1:0;
}

tcT> bool amax(T & a, const T & b) {
	return a<b?a=b, 1:0;
}

tcT> T cdiv(T a, T b) {return (a+b-1)/b;} 
 
tcTU> T ftrue(T lo, T hi, U f) { 
	while (lo < hi) { T mid = lo+(hi-lo)/2; f(mid) ? hi = mid : lo = mid+1; } 
	return lo;
}
tcTU> T ltrue(T lo, T hi, U f) {
	while (lo < hi) { T mid = lo+(hi-lo+1)/2; f(mid) ? lo = mid : hi = mid-1; } 
	return lo;
}

#define ri(...) int __VA_ARGS__; re(__VA_ARGS__);
#define rl(...) ll __VA_ARGS__; re(__VA_ARGS__);
#define rs(...) str __VA_ARGS__; re(__VA_ARGS__);

const int mxn = 2e5 + 10; 
const int inf = 1e9 + 10; 
const int M = 998244353;

const ld eps = 1e-12; 

void solve() {
	ri(n, m, k); 
	vt<pii> a(n), b(m);
	re(a, b); 

	sort(a, [](pii & aa, pii & bb) {
		return (aa.fs * (bb.fs + bb.sc) > bb.fs * (aa.fs + aa.sc)); 
	});
	sort(b, [](pii & aa, pii & bb) {
		return (aa.fs * (bb.fs + bb.sc) > bb.fs * (aa.fs + aa.sc)); 
	});

	function<long double(int, int)> Comb = [&] (int i, int j) { 
		ld w = a[i].fs, x = a[i].sc, y = b[j].fs,  z = b[j].sc; 
		// ps((w + x) / (w + x + y + z)); 
		return (w + y) / (w + x + y + z); 
	};

	function<pair<int, int>(int i, long double t)> f = [&] (int i, ld t) {
		if (Comb(i, 0) < t) return MP(0, 0); 
		pii ret; 
		int lo = 0, hi = m - 1; 
		while (lo < hi) {
			int md = lo + (hi - lo + 1) / 2; 
			if (Comb(i, md) > t || Comb(i, md) + eps > t) lo = md; 
			else hi = md - 1; 
		}
		if (lo == 0) ret.fs = (Comb(i, 0) > t ? 1 : 0); 
		else ret.fs = lo + 1; 

		lo = 0, hi = m - 1;
		while (lo < hi) {
			int md = lo + (hi - lo + 1) / 2; 
			if (Comb(i, md) > t || abs(Comb(i, md) - t) < eps) lo = md; 
			else hi = md - 1; 
		}
		if (lo == 0) ret.sc = ((Comb(i, 0) > t || abs(Comb(i, 0) - t) < eps) ? 1 : 0); 
		ret.sc = lo + 1; 
		return ret;  
	};

	cout << fixed << setprecision(30); 

	ld lo = 0.000000009, hi = 0.999999991;
	while (hi - lo > eps) { 
		ld md = lo + (hi - lo) / 2; //lasttrue (cnt < / <= md) <= k; 
		ll cnt = 0, eq = 0; 
		rp(i, n) {
			pii p = f(i, md); 
			cnt += p.fs; 
			eq += p.sc - p.fs; 
		}
		if (cnt + eq < k) hi = md; 
		else lo = md; 
	}

	cout << (lo * (ld) 100) << '\n'; 

	// ll cnt = 0, eq = 0; 
	// rp(i, n) {
	// 	pii p = f(i, (ld)0.625); 
	// 	cnt += p.fs; 
	// 	eq += p.sc - p.fs; 
	// 	rp(j, m) {
	// 		ps(a[i], b[j], Comb(i, j)); 
	// 	}
	// }
	// ps(cnt, eq); 
	// ps(lo * (ld)100); 
	// ps(a); ps(b); 
	return; 
}

int main() {
	quick; 

	int t = 1; 
	// cin >> t; 
	while (t--) solve();

	return 0; 
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/


 

Submission Info

Compile Error

./Main.cpp: In function ‘std::string to_string(std::vector<bool>)’:
./Main.cpp:51:27: warning: unnecessary parentheses in declaration of ‘i’ [-Wparentheses]
   51 | #define rp(i, e) for (int (i) = 0; (i) < (int) (e); (i)+=1)
      |                           ^
./Main.cpp:122:2: note: in expansion of macro ‘rp’
  122 |  rp(i, sz(v))
      |  ^~
./Main.cpp: In function ‘std::string to_string(std::bitset<_Nb>)’:
./Main.cpp:51:27: warning: unnecessary parentheses in declaration of ‘i’ [-Wparentheses]
   51 | #define rp(i, e) for (int (i) = 0; (i) < (int) (e); (i)+=1)
      |                           ^
./Main.cpp:128:2: note: in expansion of macro ‘rp’
  128 |  rp(i, S)
      |  ^~
./Main.cpp: In function ‘void solve()’:
./Main.cpp:51:27: warning: unnecessary parentheses in declaration of ‘i’ [-Wparentheses]
   51 | #define rp(i, e) for (int (i) = 0; (i) < (int) (e); (i)+=1)
      |                           ^
./Main.cpp:275:3: note: in expansion of macro ‘rp’
  275 |   rp(i, n) {
      |   ^~

Judge Result