QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#311199 | #8137. 'Ello, and What Are You After, Then? | ucup-team088 | WA | 1742ms | 12504kb | C++17 | 7.8kb | 2024-01-22 04:11:57 | 2024-01-22 04:11:58 |
Judging History
answer
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<cassert>
#include<complex>
#include<numeric>
#include<array>
#include<chrono>
using namespace std;
//#define int long long
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
//ll mod = 1;
constexpr ll mod = 998244353;
//constexpr ll mod = 1000000007;
const int mod17 = 1000000007;
const ll INF = (ll)mod17 * mod17;
typedef pair<int, int>P;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
using ld = double;
typedef pair<ld, ld> LDP;
const ld eps = 1e-10;
const ld pi = acosl(-1.0);
template<typename T>
void chmin(T& a, T b) {
a = min(a, b);
}
template<typename T>
void chmax(T& a, T b) {
a = max(a, b);
}
template<typename T>
vector<T> vmerge(vector<T>& a, vector<T>& b) {
vector<T> res;
int ida = 0, idb = 0;
while (ida < a.size() || idb < b.size()) {
if (idb == b.size()) {
res.push_back(a[ida]); ida++;
}
else if (ida == a.size()) {
res.push_back(b[idb]); idb++;
}
else {
if (a[ida] < b[idb]) {
res.push_back(a[ida]); ida++;
}
else {
res.push_back(b[idb]); idb++;
}
}
}
return res;
}
template<typename T>
void cinarray(vector<T>& v) {
rep(i, v.size())cin >> v[i];
}
template<typename T>
void coutarray(vector<T>& v) {
rep(i, v.size()) {
if (i > 0)cout << " "; cout << v[i];
}
cout << "\n";
}
ll mod_pow(ll x, ll n, ll m = mod) {
if (n < 0) {
ll res = mod_pow(x, -n, m);
return mod_pow(res, m - 2, m);
}
if (abs(x) >= m)x %= m;
if (x < 0)x += m;
//if (x == 0)return 0;
ll res = 1;
while (n) {
if (n & 1)res = res * x % m;
x = x * x % m; n >>= 1;
}
return res;
}
//mod should be <2^31
struct modint {
int n;
modint() :n(0) { ; }
modint(ll m) {
if (m < 0 || mod <= m) {
m %= mod; if (m < 0)m += mod;
}
n = m;
}
operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
bool operator<(modint a, modint b) { return a.n < b.n; }
modint operator+=(modint& a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= (int)mod; return a; }
modint operator-=(modint& a, modint b) { a.n -= b.n; if (a.n < 0)a.n += (int)mod; return a; }
modint operator*=(modint& a, modint b) { a.n = ((ll)a.n * b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, ll n) {
if (n == 0)return modint(1);
modint res = (a * a) ^ (n / 2);
if (n % 2)res = res * a;
return res;
}
ll inv(ll a, ll p) {
if (a == 0)return 0;
return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }
modint operator/=(modint& a, modint b) { a = a / b; return a; }
const int max_n = 1 << 20;
modint fact[max_n], factinv[max_n];
void init_f() {
fact[0] = modint(1);
for (int i = 0; i < max_n - 1; i++) {
fact[i + 1] = fact[i] * modint(i + 1);
}
factinv[max_n - 1] = modint(1) / fact[max_n - 1];
for (int i = max_n - 2; i >= 0; i--) {
factinv[i] = factinv[i + 1] * modint(i + 1);
}
}
modint comb(int a, int b) {
if (a < 0 || b < 0 || a < b)return 0;
return fact[a] * factinv[b] * factinv[a - b];
}
modint combP(int a, int b) {
if (a < 0 || b < 0 || a < b)return 0;
return fact[a] * factinv[a - b];
}
ll gcd(ll a, ll b) {
a = abs(a); b = abs(b);
if (a < b)swap(a, b);
while (b) {
ll r = a % b; a = b; b = r;
}
return a;
}
template<typename T>
void addv(vector<T>& v, int loc, T val) {
if (loc >= v.size())v.resize(loc + 1, 0);
v[loc] += val;
}
/*const int mn = 2000005;
bool isp[mn];
vector<int> ps;
void init() {
fill(isp + 2, isp + mn, true);
for (int i = 2; i < mn; i++) {
if (!isp[i])continue;
ps.push_back(i);
for (int j = 2 * i; j < mn; j += i) {
isp[j] = false;
}
}
}*/
//[,val)
template<typename T>
auto prev_itr(set<T>& st, T val) {
auto res = st.lower_bound(val);
if (res == st.begin())return st.end();
res--; return res;
}
//[val,)
template<typename T>
auto next_itr(set<T>& st, T val) {
auto res = st.lower_bound(val);
return res;
}
using mP = pair<modint, modint>;
mP operator+(mP a, mP b) {
return { a.first + b.first,a.second + b.second };
}
mP operator+=(mP& a, mP b) {
a = a + b; return a;
}
mP operator-(mP a, mP b) {
return { a.first - b.first,a.second - b.second };
}
mP operator-=(mP& a, mP b) {
a = a - b; return a;
}
LP operator+(LP a, LP b) {
return { a.first + b.first,a.second + b.second };
}
LP operator+=(LP& a, LP b) {
a = a + b; return a;
}
LP operator-(LP a, LP b) {
return { a.first - b.first,a.second - b.second };
}
LP operator-=(LP& a, LP b) {
a = a - b; return a;
}
mt19937 mt(time(0));
const string drul = "DRUL";
string senw = "SENW";
//DRUL,or SENW
//int dx[4] = { 1,0,-1,0 };
//int dy[4] = { 0,1,0,-1 };
//------------------------------------
void solve() {
int b, c, s; cin >> b >> c >> s;
int n; cin >> n;
vector<vector<int>> f(n), t(n), e(n);
rep(i, n) {
int len; cin >> len;
f[i].resize(len);
t[i].resize(len);
e[i].resize(len);
rep(j, len)cin >> f[i][j] >> t[i][j] >> e[i][j];
}
auto can = [&](ld x)->bool {
ld maup = -INF;
ld madow = -INF;
rep(i, n) {
int nsz = f[i].size(); nsz -= b; chmax(nsz, 1);
vector<ld> vs;
rep(j, f[i].size()) {
ld val = e[i][j] * t[i][j] - t[i][j] * x;
vs.push_back(val);
}
auto can2 = [&](ld vx) {
vector<ld> ts;
rep(j, f[i].size()) {
ld v = f[i][j] * (vs[j] - vx);
ts.push_back(v);
}
sort(all(ts), greater<ld>());
ts.resize(nsz);
ld sum = 0;
rep(i, ts.size())sum += ts[i];
return sum >= 0;
};
ld le = -mod17, ri = mod17;
rep(_, 60) {
ld mid = (le + ri) / 2;
if (can2(mid))le = mid;
else ri = mid;
}
chmax(maup, le);
}
if (maup >= 0)return true;
rep(i, n) {
int nsz = f[i].size(); nsz -= b; chmax(nsz, 1);
vector<ld> vs;
rep(j, f[i].size()) {
ld val = e[i][j] * t[i][j] - t[i][j] * x;
vs.push_back(val);
}
auto can3 = [&](ld vx) {
vector<ld> pre, las;
rep(j, f[i].size()) {
if (vs[j] >= 0) {
pre.push_back(f[i][j] * (vs[j]-maup));
}
else {
las.push_back(-vx * f[i][j]);
}
}
sort(all(pre), greater<ld>());
sort(all(las), greater<ld>());
vector<ld> ts;
for (auto v : pre)ts.push_back(v);
for (auto v : las)ts.push_back(v);
ts.resize(nsz);
ld sum = 0;
rep(i, ts.size())sum += ts[i];
return sum >= 0;
};
ld le = -mod17, ri = mod17;
rep(_, 60) {
ld mid = (le + ri) / 2;
if (can3(mid))le = mid;
else ri = mid;
}
chmax(madow, le);
}
//cout << x << " " << maup << " " << madow << "\n";
ld v = maup * s + madow * c;
return v >= 0;
};
ld le = 0, ri = 10000;
rep(_, 40) {
ld mid = (le + ri) / 2;
if (can(mid))le = mid;
else ri = mid;
}
cout << le << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout << fixed << setprecision(10);
//init_f();
//init();
//while(true)
//expr();
//int t; cin >> t; rep(i, t)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 12072kb
input:
0 1 6 2 1 1 1 1 2 1 10 1 1 10 10
output:
6.9999999960
result:
ok found '7.0000000', expected '7.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 2ms
memory: 12056kb
input:
2 1 2 1 4 10 2 1 10 1 1 1 10 1 1 1 10
output:
5.9090909053
result:
ok found '5.9090909', expected '5.9090909', error '0.0000000'
Test #3:
score: -100
Wrong Answer
time: 1742ms
memory: 12504kb
input:
14 1000 1000 1000 30 113 80 1188 92 145 1074 130 56 1296 139 102 1142 60 76 1317 128 126 1208 73 120 1155 91 89 1197 115 64 979 80 118 592 110 97 556 83 105 578 94 51 848 98 134 757 107 138 1038 105 143 892 92 72 893 88 103 961 87 148 879 105 84 823 85 134 607 100 82 1084 199 58 801 138 85 743 214 1...
output:
1424.2190374262
result:
wrong answer 1st numbers differ - expected: '1453.3645790', found: '1424.2190374', error = '0.0200538'