結果

問題 No.5020 Averaging
コンテスト
ユーザー Rafbill
提出日時 2024-02-25 14:45:28
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 10,863 bytes
コンパイル時間 3,212 ms
コンパイル使用メモリ 178,668 KB
実行使用メモリ 108,236 KB
スコア 3,426,011
最終ジャッジ日時 2024-02-25 14:46:07
合計ジャッジ時間 20,028 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge10
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 TLE * 7 -- * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

// -*- 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 <bits/stdc++.h>
 #include <sys/time.h>
 #include <immintrin.h>
 #include <x86intrin.h>
// 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<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 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<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 << x << " " << y << endl;
  }
}
void solve(){
  vector<p2> L, R;
  for(i32 i = (1); i <= (i32)(40); ++i) {
    p2 p = p2(A[i]/100,B[i]/100,(1ll<<i));
    if(i&1) L.emplace_back(p);
    else R.emplace_back(p);
  }
  L = build(L);
  R = build(R);
  filter(L, [&](auto const& p) { return __builtin_popcount(p.m) == 7; });
  filter(R, [&](auto const& p) { return __builtin_popcount(p.m) == 8; });
  i64 nl = L.size();
  i64 nr = R.size();
  i64 x0 = (16*5e17 - A[0])/100;
  i64 y0 = (16*5e17 - B[0])/100;
  auto test = [&](i64 limit) -> bool {
    i64 ir0 = 0, ir1 = 0;
    multiset<i64> ys;
    for(i32 il = (nl-1); il >= (i32)(0); --il) {
      while(ir1<nr && L[il].x+R[ir1].x <= x0+limit) {
        ys.insert(R[ir1].y);
        ir1 += 1;
      }
      while(ir0<nr && L[il].x+R[ir0].x < x0-limit) {
        ys.erase(ys.find(R[ir0].y));
        ir0 += 1;
      }
      auto it = ys.lower_bound(y0-L[il].y - limit);
      if(it != end(ys) && *it <= (y0-L[il].y + limit)) return true;
    }
    return false;
  };
  i64 lo = 0, hi = 2e18;
  while(lo != hi) {
    i64 mi = (lo+hi)/2;
    if(test(mi)) hi = mi;
    else lo = mi+1;
  }
  auto recon = [&](i64 limit) {
    i64 ir0 = 0, ir1 = 0;
    multiset<i64> ys;
    for(i32 il = (nl-1); il >= (i32)(0); --il) {
      while(ir1<nr && L[il].x+R[ir1].x <= x0+limit) {
        ys.insert(R[ir1].y);
        ir1 += 1;
      }
      while(ir0<nr && L[il].x+R[ir0].x < x0-limit) {
        ys.erase(ys.find(R[ir0].y));
        ir0 += 1;
      }
      auto it = ys.lower_bound(y0-L[il].y - limit);
      if(it != end(ys) && *it <= (y0-L[il].y + limit)) {
        for(i32 ir = (ir0); ir <= (i32)(ir1-1); ++ir) {
          if(y0-L[il].y-limit <= R[ir].y && R[ir].y <= y0-L[il].y+limit) {
            auto p = L[il]+R[ir]+p2(A[0]/100, B[0]/100, 1);
            vector<i32> I;
            for(i32 i = 0; i < (i32)(N); ++i) if(p.m&(1<<i)) I.emplace_back(i);
            vector<array<i32,2>> ans;
            for(i32 i = 0; i < (i32)(4); ++i) {
              for(i32 j = 0; j < 16; j += 2<<i) {
                ans.push_back({1+I[j],1+I[j+(1<<i)]});
              }
            }
            print_answer(ans);
            return;
          }
        }
      }
    }
  };
  recon(lo);
}
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