結果

問題 No.5020 Averaging
コンテスト
ユーザー Rafbill
提出日時 2024-02-25 15:45:03
言語 C++14
(gcc 13.3.0 + boost 1.87.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
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます
コンパイルメッセージ
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) {
      |            ^

ソースコード

diff # 

#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;
}
0