// -*- compile-command: "$HOME/CompetitiveProgramming/Library/compile.sh main -std=c++20 -Wall -Wextra -O3 -g -march=native -DLOCAL -ffast-math -Wno-deprecated-enum-float-conversion" -*- #pragma GCC optimize "-O3,omit-frame-pointer,inline,unroll-all-loops,fast-math" #pragma GCC target "tune=native" #include #include #include #include // double TL_SIMPLEX = 2.9; // float get_elapsed(); // Qi Huangfu's simplex solver (https://github.com/jajhall/hsol/tree/master) // (MIT License) // #include "hsol/HDual.cpp" // #include "hsol/HDualMulti.cpp" // #include "hsol/HDualRHS.cpp" // #include "hsol/HDualRow.cpp" // #include "hsol/HFactor.cpp" // #include "hsol/HMatrix.cpp" // #include "hsol/HModel.cpp" // #include "hsol/HPrimal.cpp" // #include "hsol/HVector.cpp" // #ifndef CP_GEN // #define BACKWARD_HAS_BFD 1 // #include "backward.hpp" // backward::SignalHandling sh; // #endif using namespace std; // Macros using i8 = int8_t; using u8 = uint8_t; using i16 = int16_t; using u16 = uint16_t; using i32 = int32_t; using u32 = uint32_t; using i64 = int64_t; using u64 = uint64_t; using f32 = float; using f64 = double; // Types template using min_queue = priority_queue, greater>; template using max_queue = priority_queue; // Printing template void print_collection(ostream& out, T const& x); template void print_tuple(ostream& out, T const& a, index_sequence); namespace std { template ostream& operator<<(ostream& out, tuple const& x) { print_tuple(out, x, index_sequence_for{}); return out; } template ostream& operator<<(ostream& out, pair const& x) { print_tuple(out, x, index_sequence_for{}); return out; } template ostream& operator<<(ostream& out, array const& x) { print_collection(out, x); return out; } template ostream& operator<<(ostream& out, vector const& x) { print_collection(out, x); return out; } template ostream& operator<<(ostream& out, deque const& x) { print_collection(out, x); return out; } template ostream& operator<<(ostream& out, multiset const& x) { print_collection(out, x); return out; } template ostream& operator<<(ostream& out, multimap const& x) { print_collection(out, x); return out; } template ostream& operator<<(ostream& out, set const& x) { print_collection(out, x); return out; } template ostream& operator<<(ostream& out, map const& x) { print_collection(out, x); return out; } template ostream& operator<<(ostream& out, unordered_set const& x) { print_collection(out, x); return out; } } template void print_tuple(ostream& out, T const& a, index_sequence){ using swallow = int[]; out << '('; (void)swallow{0, (void(out << (I == 0? "" : ", ") << get(a)), 0)...}; out << ')'; } template void print_collection(ostream& out, T const& x) { int f = 0; out << '['; for(auto const& i: x) { out << (f++ ? "," : ""); out << i; } out << "]"; } // Random struct RNG { uint64_t s[2]; RNG(u64 seed) { reset(seed); } RNG() { reset(time(0)); } using result_type = u32; constexpr u32 min(){ return numeric_limits::min(); } constexpr u32 max(){ return numeric_limits::max(); } u32 operator()() { return randomInt32(); } static __attribute__((always_inline)) inline uint64_t rotl(const uint64_t x, int k) { return (x << k) | (x >> (64 - k)); } inline void reset(u64 seed) { struct splitmix64_state { u64 s; u64 splitmix64() { u64 result = (s += 0x9E3779B97f4A7C15); result = (result ^ (result >> 30)) * 0xBF58476D1CE4E5B9; result = (result ^ (result >> 27)) * 0x94D049BB133111EB; return result ^ (result >> 31); } }; splitmix64_state sm { seed }; s[0] = sm.splitmix64(); s[1] = sm.splitmix64(); } uint64_t next() { const uint64_t s0 = s[0]; uint64_t s1 = s[1]; const uint64_t result = rotl(s0 * 5, 7) * 9; s1 ^= s0; s[0] = rotl(s0, 24) ^ s1 ^ (s1 << 16); // a, b s[1] = rotl(s1, 37); // c return result; } inline u32 randomInt32() { return next(); } inline u64 randomInt64() { return next(); } inline u32 random32(u32 r) { return (((u64)randomInt32())*r)>>32; } inline u64 random64(u64 r) { return randomInt64()%r; } inline u32 randomRange32(u32 l, u32 r) { return l + random32(r-l+1); } inline u64 randomRange64(u64 l, u64 r) { return l + random64(r-l+1); } inline double randomDouble() { return (double)randomInt32() / 4294967296.0; } inline float randomFloat() { return (float)randomInt32() / 4294967296.0; } inline double randomRangeDouble(double l, double r) { return l + randomDouble() * (r-l); } template void shuffle(vector& v) { i32 sz = v.size(); for(i32 i = sz; i > 1; i--) { i32 p = random32(i); swap(v[i-1],v[p]); } } template void shuffle(T* fr, T* to) { i32 sz = distance(fr,to); for(int i = sz; i > 1; i--) { int p = random32(i); swap(fr[i-1],fr[p]); } } template inline int sample_index(vector const& v) { return random32(v.size()); } template inline T sample(vector const& v) { return v[sample_index(v)]; } } rng; // Letrec template class letrec_result { Fun fun_; public: template explicit letrec_result(T &&fun): fun_(forward(fun)) {} template decltype(auto) operator()(Args &&...args) { return fun_(ref(*this), forward(args)...); } }; template decltype(auto) letrec(Fun &&fun) { return letrec_result>(forward(fun)); } // Timer struct timer { chrono::high_resolution_clock::time_point t_begin; timer() { t_begin = chrono::high_resolution_clock::now(); } void reset() { t_begin = chrono::high_resolution_clock::now(); } float elapsed() const { return chrono::duration(chrono::high_resolution_clock::now() - t_begin).count(); } }; // Util template T& smin(T& x, T const& y) { x = min(x,y); return x; } template T& smax(T& x, T const& y) { x = max(x,y); return x; } template int sgn(T val) { if(val < 0) return -1; if(val > 0) return 1; return 0; } static inline string int_to_string(int val, int digits = 0) { string s = to_string(val); reverse(begin(s), end(s)); while((int)s.size() < digits) s.push_back('0'); reverse(begin(s), end(s)); return s; } // Debug static inline void debug_impl_seq() { cerr << "}"; } template void debug_impl_seq(T const& t, V const&... v) { cerr << t; if(sizeof...(v)) { cerr << ", "; } debug_impl_seq(v...); } const f64 TL1 = 0.9; timer TM; const i32 N = 45; i64 A[N], B[N]; void read(){ i32 n; cin>>n; do { if(!(n == N)) { throw runtime_error("main.cpp" ":" "11" " Assertion failed: " "n == N"); } } while(0); for(i32 i = 0; i < (i32)(N); ++i) cin>>A[i]>>B[i]; } struct p2 { i64 x,y; i64 m; p2(i64 x_, i64 y_, i64 m_){ x = x_; y = y_; m = m_; } p2() { x = y = m = 0; } p2& operator+=(p2 const& o) { x += o.x; y += o.y; m |= o.m; return *this; } p2 operator+(p2 const& o) const{ p2 r = *this; r += o; return r; } }; vector merge(vector const& A, vector const& B){ i64 ia = 0, ib = 0; i64 na = A.size(), nb = B.size(); vector out; out.reserve(na+nb); while(ia build(vector X) { vector Y = {p2()}; for(auto const& x : X) { auto L = Y, R = Y; for(auto& p : R) p += x; Y = merge(L, R); } return Y; } template void filter(V &v, Pred pred) { i32 sz = 0; for(i32 i = 0; i < (i32)(v.size()); ++i) if(pred(v[i])) { v[sz++] = v[i]; } v.resize(sz); } void print_answer(vector> ans) { cout << ans.size() << endl; for(auto [x,y] : ans) { cout << x << " " << y << endl; } } void solve(){ vector L, R; for(i32 i = (1); i <= (i32)(40); ++i) { p2 p = p2(A[i]/100,B[i]/100,(1ll< bool { i64 ir0 = 0, ir1 = 0; multiset ys; for(i32 il = (nl-1); il >= (i32)(0); --il) { while(ir1 ys; for(i32 il = (nl-1); il >= (i32)(0); --il) { while(ir1 I; for(i32 i = 0; i < (i32)(N); ++i) if(p.m&(1<> ans; for(i32 i = 0; i < (i32)(4); ++i) { for(i32 j = 0; j < 16; j += 2<