Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <chrono>
- using namespace std;
- using namespace std::chrono;
- // #pragma GCC target ("avx2")
- // #pragma GCC optimization ("O3")
- // #pragma GCC optimization ("unroll-loops")
- // #pragma optimization_level 3
- // #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
- // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- #define f0r(a, b) for (long long a = 0; a < (b); ++a)
- #define f1r(a, b, c) for (long long a = (b); a < (c); ++a)
- #define f0rd(a, b) for (long long a = (b); a >= 0; --a)
- #define f1rd(a, b, c) for (long long a = (b); a >= (c); --a)
- #define ms(arr, v) memset(arr, v, sizeof(arr))
- #define pb push_back
- #define send {ios_base::sync_with_stdio(false);}
- #define help {cin.tie(NULL); cout.tie(NULL);}
- #define fix(prec) {cout << setprecision(prec) << fixed;}
- #define mp make_pair
- #define f first
- #define s second
- #define all(v) v.begin(), v.end()
- #define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());}
- #define readgraph(list, edges) for (int i = 0; i < edges; i++) {int a, b; cin >> a >> b; a--; b--; list[a].pb(b); list[b].pb(a);}
- #define ai(a, n) for (int ele = 0; ele < n; ele++) cin >> a[ele];
- #define ain(a, lb, rb) for (int ele = lb; ele <= rb; ele++) cin >> a[ele];
- #define ao(a, n) {for (int ele = 0; ele < (n); ele++) { if (ele) cout << " "; cout << a[ele]; } cout << '\n';}
- #define aout(a, lb, rb) {for (int ele = (lb); ele <= (rb); ele++) { if (ele > (lb)) cout << " "; cout << a[ele]; } cout << '\n';}
- #define vsz(x) ((long long) x.size())
- typedef long long ll;
- typedef double ld;
- typedef long double lld;
- typedef unsigned long long ull;
- typedef pair<int, int> pii;
- typedef pair<ll, ll> pll;
- typedef vector<int> vi;
- typedef vector<ll> vl;
- typedef vector<pii> vpi;
- typedef vector<pll> vpl;
- template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v);
- template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
- template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
- cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
- }
- template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
- cin >> p.first;
- return cin >> p.second;
- }
- // mt19937 rng(steady_clock::now().time_since_epoch().count());
- mt19937 rng(61378913);
- /* usage - just do rng() */
- void usaco(string filename) {
- // #pragma message("be careful, freopen may be wrong")
- freopen((filename + ".in").c_str(), "r", stdin);
- freopen((filename + ".out").c_str(), "w", stdout);
- }
- const lld pi = 3.14159265358979323846;
- const ll mod = 1000000007;
- // const ll mod = 998244353;
- // ll mod;
- ll n, m, k, q, l, r, x, y, z;
- lld a[1000005];
- lld b[1000005];
- lld c[1000005];
- string s, t;
- ll ans = 0;
- const int N = 5;
- const int MX = 100000;
- const int MXG = 100000;
- const lld EPS = 1e-6;
- ll rn() {
- return ((ll)rng() << 21) + rng();
- }
- void gen() {
- f0r(i, N) {
- a[i] = rn() % MX + 1;
- b[i] = rn() % MX + 1;
- c[i] = rn() % MXG + 1;
- }
- a[N] = mod * mod;
- b[N] = mod * mod;
- c[N] = 0;
- }
- pair<lld, lld> solve_fast() {
- lld sum1=0,sum2=0;
- for(int i=0;i<N;i++){
- sum1+=(c[i]/(a[i]+b[i]))*b[i];
- sum2+=(c[i]/(a[i]+b[i]))*a[i];
- }
- return mp(sum1, sum2);
- }
- /* O((N!)^2) */
- pair<lld, lld> solve_slow() {
- lld best = 0;
- int perm1[N], perm2[N];
- iota(perm1, perm1 + N, 0);
- do {
- lld cworst = mod * mod; // INF
- iota(perm2, perm2 + N, 0);
- do {
- lld left__[N + 1];
- f0r(i, N + 1) left__[i] = 1;
- int pt1 = 0, pt2 = 0;
- lld cur = 0;
- while (1) {
- int pos1 = N, pos2 = N;
- if (pt1 < N) pos1 = perm1[pt1];
- if (pt2 < N) pos2 = perm2[pt2];
- if (pt1 == N && pt2 == N) break;
- lld ntime;
- lld rate1 = 1 / a[pos1];
- lld rate2 = 1 / b[pos2];
- if (pos1 == pos2) {
- ntime = left__[pos1] / (rate1 + rate2);
- } else {
- ntime = min(left__[pos1] / rate1, left__[pos2] / rate2);
- }
- lld prog1 = ntime * rate1;
- lld prog2 = ntime * rate2;
- cur += prog1 * c[pos1];
- left__[pos1] -= prog1;
- left__[pos2] -= prog2;
- while (pt1 < N && left__[perm1[pt1]] < EPS) {
- ++pt1;
- }
- while (pt2 < N && left__[perm2[pt2]] < EPS) {
- ++pt2;
- }
- }
- cworst = min(cworst, cur);
- } while (next_permutation(perm2, perm2 + N));
- best = max(best, cworst);
- } while (next_permutation(perm1, perm1 + N));
- lld tot = 0;
- f0r(i, N) tot += c[i];
- return mp(best, tot - best);
- }
- void solve(int tc) {
- int count = 0;
- while (1) {
- ++count;
- gen();
- pair<lld, lld> ans1 = solve_fast();
- pair<lld, lld> ans2 = solve_slow();
- if (abs(ans1.f - ans2.f) > EPS || abs(ans1.s - ans2.s) > EPS) {
- cout << "FAILED " << count << endl;
- fix(0);
- f0r(i, N) {
- cout << c[i] << " " << a[i] << " " << b[i] << endl;
- }
- fix(15);
- cout << ans1 << " " << ans2 << endl;
- return;
- }
- cout << "PASSED " << count << endl;
- }
- }
- int main() {
- send help
- // usaco("cowland");
- int tc = 1;
- // cin >> tc;
- for (int t = 0; t < tc; t++) solve(t);
- }
Add Comment
Please, Sign In to add comment