結果
問題 | No.5020 Averaging |
ユーザー | Rafbill |
提出日時 | 2024-02-25 15:45:03 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 953 ms / 1,000 ms |
コード長 | 9,639 bytes |
コンパイル時間 | 4,900 ms |
コンパイル使用メモリ | 371,012 KB |
実行使用メモリ | 6,548 KB |
スコア | 75,237,861 |
最終ジャッジ日時 | 2024-02-25 15:46:00 |
合計ジャッジ時間 | 55,795 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
純コード判定しない問題か言語 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 952 ms
6,548 KB |
testcase_01 | AC | 952 ms
6,548 KB |
testcase_02 | AC | 952 ms
6,548 KB |
testcase_03 | AC | 952 ms
6,548 KB |
testcase_04 | AC | 952 ms
6,548 KB |
testcase_05 | AC | 952 ms
6,548 KB |
testcase_06 | AC | 952 ms
6,548 KB |
testcase_07 | AC | 952 ms
6,548 KB |
testcase_08 | AC | 952 ms
6,548 KB |
testcase_09 | AC | 951 ms
6,548 KB |
testcase_10 | AC | 952 ms
6,548 KB |
testcase_11 | AC | 952 ms
6,548 KB |
testcase_12 | AC | 952 ms
6,548 KB |
testcase_13 | AC | 951 ms
6,548 KB |
testcase_14 | AC | 952 ms
6,548 KB |
testcase_15 | AC | 952 ms
6,548 KB |
testcase_16 | AC | 952 ms
6,548 KB |
testcase_17 | AC | 952 ms
6,548 KB |
testcase_18 | AC | 953 ms
6,548 KB |
testcase_19 | AC | 952 ms
6,548 KB |
testcase_20 | AC | 952 ms
6,548 KB |
testcase_21 | AC | 952 ms
6,548 KB |
testcase_22 | AC | 952 ms
6,548 KB |
testcase_23 | AC | 953 ms
6,548 KB |
testcase_24 | AC | 952 ms
6,548 KB |
testcase_25 | AC | 952 ms
6,548 KB |
testcase_26 | AC | 952 ms
6,548 KB |
testcase_27 | AC | 952 ms
6,548 KB |
testcase_28 | AC | 952 ms
6,548 KB |
testcase_29 | AC | 951 ms
6,548 KB |
testcase_30 | AC | 952 ms
6,548 KB |
testcase_31 | AC | 952 ms
6,548 KB |
testcase_32 | AC | 952 ms
6,548 KB |
testcase_33 | AC | 952 ms
6,548 KB |
testcase_34 | AC | 952 ms
6,548 KB |
testcase_35 | AC | 952 ms
6,548 KB |
testcase_36 | AC | 953 ms
6,548 KB |
testcase_37 | AC | 952 ms
6,548 KB |
testcase_38 | AC | 952 ms
6,548 KB |
testcase_39 | AC | 951 ms
6,548 KB |
testcase_40 | AC | 952 ms
6,548 KB |
testcase_41 | AC | 952 ms
6,548 KB |
testcase_42 | AC | 951 ms
6,548 KB |
testcase_43 | AC | 952 ms
6,548 KB |
testcase_44 | AC | 952 ms
6,548 KB |
testcase_45 | AC | 952 ms
6,548 KB |
testcase_46 | AC | 952 ms
6,548 KB |
testcase_47 | AC | 952 ms
6,548 KB |
testcase_48 | AC | 952 ms
6,548 KB |
testcase_49 | AC | 952 ms
6,548 KB |
コンパイルメッセージ
main.cpp: In function 'void print_answer(std::vector<std::array<int, 2> >)': main.cpp:284:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 284 | for(auto [x,y] : ans) { | ^
ソースコード
#pragma GCC optimize "-O3,omit-frame-pointer,inline,unroll-all-loops,fast-math" #pragma GCC target "tune=native" #include <bits/stdc++.h> #include <sys/time.h> #include <immintrin.h> #include <x86intrin.h> 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<class T> using min_queue = priority_queue<T, vector<T>, greater<T>>; template<class T> using max_queue = priority_queue<T>; // Printing template<class T> void print_collection(ostream& out, T const& x); template<class T, size_t... I> void print_tuple(ostream& out, T const& a, index_sequence<I...>); namespace std { template<class... A> ostream& operator<<(ostream& out, tuple<A...> const& x) { print_tuple(out, x, index_sequence_for<A...>{}); return out; } template<class... A> ostream& operator<<(ostream& out, pair<A...> const& x) { print_tuple(out, x, index_sequence_for<A...>{}); return out; } template<class A, size_t N> ostream& operator<<(ostream& out, array<A, N> const& x) { print_collection(out, x); return out; } template<class A> ostream& operator<<(ostream& out, vector<A> const& x) { print_collection(out, x); return out; } template<class A> ostream& operator<<(ostream& out, deque<A> const& x) { print_collection(out, x); return out; } template<class A> ostream& operator<<(ostream& out, multiset<A> const& x) { print_collection(out, x); return out; } template<class A, class B> ostream& operator<<(ostream& out, multimap<A, B> const& x) { print_collection(out, x); return out; } template<class A> ostream& operator<<(ostream& out, set<A> const& x) { print_collection(out, x); return out; } template<class A, class B> ostream& operator<<(ostream& out, map<A, B> const& x) { print_collection(out, x); return out; } template<class A, class B> ostream& operator<<(ostream& out, unordered_set<A> const& x) { print_collection(out, x); return out; } } template<class T, size_t... I> void print_tuple(ostream& out, T const& a, index_sequence<I...>){ using swallow = int[]; out << '('; (void)swallow{0, (void(out << (I == 0? "" : ", ") << get<I>(a)), 0)...}; out << ')'; } template<class T> 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<u32>::min(); } constexpr u32 max(){ return numeric_limits<u32>::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<class T> void shuffle(vector<T>& v) { i32 sz = v.size(); for(i32 i = sz; i > 1; i--) { i32 p = random32(i); swap(v[i-1],v[p]); } } template<class T> 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<class T> inline int sample_index(vector<T> const& v) { return random32(v.size()); } template<class T> inline T sample(vector<T> const& v) { return v[sample_index(v)]; } } rng; // Letrec template<class Fun> class letrec_result { Fun fun_; public: template<class T> explicit letrec_result(T &&fun): fun_(forward<T>(fun)) {} template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(ref(*this), forward<Args>(args)...); } }; template<class Fun> decltype(auto) letrec(Fun &&fun) { return letrec_result<decay_t<Fun>>(forward<Fun>(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<float>(chrono::high_resolution_clock::now() - t_begin).count(); } }; // Util template<class T> T& smin(T& x, T const& y) { x = min(x,y); return x; } template<class T> T& smax(T& x, T const& y) { x = max(x,y); return x; } template<typename T> 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 <class T, class... V> void debug_impl_seq(T const& t, V const&... v) { cerr << t; if(sizeof...(v)) { cerr << ", "; } debug_impl_seq(v...); } const f64 TL = 0.95; 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" ":" "10" " 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<p2> merge(vector<p2> const& A, vector<p2> const& B){ i64 ia = 0, ib = 0; i64 na = A.size(), nb = B.size(); vector<p2> out; out.reserve(na+nb); while(ia<na && ib<nb) { if(A[ia].x<B[ib].x) { out.emplace_back(A[ia]); ia++; } else { out.emplace_back(B[ib]); ib++; } } while(ia<na) { out.emplace_back(A[ia]); ia++; } while(ib<nb) { out.emplace_back(B[ib]); ib++; } return out; } vector<p2> build(vector<p2> X) { vector<p2> 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<typename V, typename Pred> 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<array<i32,2>> ans) { cout << ans.size() << endl; for(auto [x,y] : ans) { cout << 1+x << " " << 1+y << endl; } } long double w[N]; i32 I[N]; void solve(){ for(i32 i = 0; i < (i32)(N); ++i) w[i] = 1.0 / (long double)(2ll<<i); w[N-1] = w[N-2]; for(i32 i = 0; i < (i32)(N); ++i) I[i] = i; rng.shuffle(I,I+N); f64 goal = 5e17; f64 curx = -goal, cury = -goal; for(i32 i = 0; i < (i32)(N); ++i) curx += w[i] * A[I[i]]; for(i32 i = 0; i < (i32)(N); ++i) cury += w[i] * B[I[i]]; f64 score = max(abs(curx), abs(cury)); f64 best_score = score; i64 iter = 0; f64 temp = 0; while(TM.elapsed() < TL) { iter++; if(iter % 1024 == 0) { f64 done = TM.elapsed() / TL; temp = 1e16 * pow(1e5 / 1e16, done); } auto accept = [&](f64 nscore) -> bool { if(nscore < best_score) { best_score = nscore; do { cerr << "main.cpp" ":" "108" " {" << "best_score" << "} = {"; debug_impl_seq(best_score); cerr << endl << flush; } while(0); } f64 delta = nscore - score; if(delta <= 0 || rng.randomDouble() * temp > delta) { return 1; } return 0; }; i32 i = rng.random32(N), j = rng.random32(N); if(i == j) continue; f64 ncurx = curx + (w[j]-w[i])*A[I[i]] + (w[i]-w[j])*A[I[j]]; f64 ncury = cury + (w[j]-w[i])*B[I[i]] + (w[i]-w[j])*B[I[j]]; f64 nscore = max(abs(ncurx), abs(ncury)); if(accept(nscore)) { swap(I[i],I[j]); score = nscore; curx = ncurx; cury = ncury; } } do { cerr << "main.cpp" ":" "131" " {" << "iter, score" << "} = {"; debug_impl_seq(iter, score); cerr << endl << flush; } while(0); vector<array<i32,2>> ans; for(i32 i = (N-2); i >= (i32)(0); --i) { ans.push_back({I[i],I[i+1]}); I[i] = min(I[i],I[i+1]); } print_answer(ans); } i32 main(){ ios::sync_with_stdio(false); cin.tie(0); TM.reset(); read(); solve(); cerr << "Elapsed: " << TM.elapsed() << endl; cerr << "[DATA] time = " << TM.elapsed() << endl; return 0; }