結果

問題 No.5020 Averaging
ユーザー RafbillRafbill
提出日時 2024-02-25 14:54:40
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 970 ms / 1,000 ms
コード長 10,133 bytes
コンパイル時間 4,779 ms
コンパイル使用メモリ 383,724 KB
実行使用メモリ 52,612 KB
スコア 26,778,779
最終ジャッジ日時 2024-02-25 14:55:13
合計ジャッジ時間 28,654 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 259 ms
52,612 KB
testcase_01 AC 420 ms
52,612 KB
testcase_02 AC 408 ms
52,612 KB
testcase_03 AC 575 ms
52,612 KB
testcase_04 AC 222 ms
52,612 KB
testcase_05 AC 645 ms
52,612 KB
testcase_06 AC 424 ms
52,612 KB
testcase_07 AC 431 ms
52,612 KB
testcase_08 AC 396 ms
52,612 KB
testcase_09 AC 337 ms
52,612 KB
testcase_10 AC 410 ms
52,612 KB
testcase_11 AC 242 ms
52,612 KB
testcase_12 AC 382 ms
52,612 KB
testcase_13 AC 970 ms
52,612 KB
testcase_14 AC 329 ms
52,612 KB
testcase_15 AC 272 ms
52,612 KB
testcase_16 AC 228 ms
52,612 KB
testcase_17 AC 478 ms
52,612 KB
testcase_18 AC 465 ms
52,612 KB
testcase_19 AC 475 ms
52,612 KB
testcase_20 AC 573 ms
52,612 KB
testcase_21 AC 448 ms
52,612 KB
testcase_22 AC 457 ms
52,612 KB
testcase_23 AC 607 ms
52,612 KB
testcase_24 AC 383 ms
52,612 KB
testcase_25 AC 284 ms
52,612 KB
testcase_26 AC 660 ms
52,612 KB
testcase_27 AC 543 ms
52,612 KB
testcase_28 AC 414 ms
52,612 KB
testcase_29 AC 314 ms
52,612 KB
testcase_30 AC 357 ms
52,612 KB
testcase_31 AC 406 ms
52,612 KB
testcase_32 AC 599 ms
52,612 KB
testcase_33 AC 538 ms
52,612 KB
testcase_34 AC 381 ms
52,612 KB
testcase_35 AC 348 ms
52,612 KB
testcase_36 AC 472 ms
52,612 KB
testcase_37 AC 540 ms
52,612 KB
testcase_38 AC 398 ms
52,612 KB
testcase_39 AC 263 ms
52,612 KB
testcase_40 AC 326 ms
52,612 KB
testcase_41 AC 517 ms
52,612 KB
testcase_42 AC 271 ms
52,612 KB
testcase_43 AC 537 ms
52,612 KB
testcase_44 AC 487 ms
52,612 KB
testcase_45 AC 413 ms
52,612 KB
testcase_46 AC 240 ms
52,612 KB
testcase_47 AC 642 ms
52,612 KB
testcase_48 AC 523 ms
52,612 KB
testcase_49 AC 622 ms
52,612 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) {
      |            ^

ソースコード

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 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("main2.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 << x << " " << y << endl;
  }
}
void solve(){
  vector<p2> L, R;
  for(i32 i = (1); i <= (i32)(38); ++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