結果

問題 No.5020 Averaging
ユーザー tombo_
提出日時 2025-04-29 10:01:22
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 972 ms / 1,000 ms
コード長 4,074 bytes
コンパイル時間 2,335 ms
コンパイル使用メモリ 206,040 KB
実行使用メモリ 7,844 KB
スコア 25,718,880
最終ジャッジ日時 2025-04-29 10:02:17
合計ジャッジ時間 54,158 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define OVERLOAD_REP(_1, _2, _3, name, ...) name
#define REP1(i, n) for (auto i = std::decay_t<decltype(n)>{}; (i) != (n); ++(i))
#define REP2(i, l, r) for (auto i = (l); (i) != (r); ++(i))
#define rep(...) OVERLOAD_REP(__VA_ARGS__, REP2, REP1)(__VA_ARGS__)
#define REP(i, l, r) rep(i, l, r+1)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
using ll = long long;
using ld = long double;
using P = pair<ll,ll>;
struct Edge {
  int to; ll w;
};
using Graph = vector<vector<int> >;
//using Graph = vector<vector<Edge> >;
const ll INF = 2e18;
//const int INF = 2e9;
template<class T> using vc = vector<T>;
template<class T> using vv = vector<vector<T> >;
template<class T> using vvv = vector<vector<vector<T> > >;
template<class T> using pq = priority_queue<T>;
template<class T> using pq_g = priority_queue<T, vc<T>, greater<T> >;
template<class T> istream& operator>>(istream& i, vc<T>& v) { rep(j, 0, v.size()) i>>v[j]; return i; }
template<class T> ostream& operator<<(ostream& o, vc<T>& v) { rep(j, 0, v.size()) o<<v[j]<<" "; return o; }
template<class T> bool chmin(T& a, T b) {
  if(a > b) {
      a = b;
      return true;
  }
  return false;
}
template<class T> bool chmax(T& a, T b) {
  if(a < b) {
      a = b;
      return true;
  }
  return false;
}

class Timer{
    chrono::system_clock::time_point start;
    public:
        Timer() : start(chrono::system_clock::now()) {}

        double count(){
            chrono::duration<double> Time_ = chrono::system_clock::now() - start;
            return Time_.count();
        }

        bool is_under(double x){
            return (this -> count()) < x;
        }
};
// std::uniform_int_distributionを利用した一様乱数生成クラス
class Random_Gen{
    random_device seed_gen;
    mt19937 engine;
    uniform_int_distribution<int64_t> dist;
    public:
        // Constructor [l,r]で生成する値の範囲を指定
        Random_Gen() : engine(seed_gen()) {}
        Random_Gen(int64_t l, int64_t r) : engine(seed_gen()), dist(l,r) {}

        // 現在の生成する値の範囲をstd::pairで返す
        pair<int64_t,int64_t> get_range(){
            return make_pair(dist.min(),dist.max());
        }
        // 生成する値の範囲を[l,r]に変更する
        void set_range(int64_t l, int64_t r){
            uniform_int_distribution<int64_t>::param_type Param(l,r);
            dist.param(Param);
        }
        // [l,r]内の一様分布の整数を返す
        int64_t gen(){
            return dist(engine);
        }
        int64_t operator()(){ return gen(); }
};
ll mokuhyo=500000000000000000ll;
ll score(vc<ll> A, vc<ll> B, vc<ll>& u, vc<ll>& v) {
  int X = u.size();
  int N = A.size();
  rep(i, 0, X) {
    A[u[i]] = A[v[i]] = (A[u[i]]+A[v[i]])/2;
    B[u[i]] = B[v[i]] = (B[u[i]]+B[v[i]])/2;
  }
  return max(abs(A[0]-mokuhyo), abs(B[0]-mokuhyo));
}
int main() {
  // 高速化
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  // 小数点の出力桁数を指定
  cout << fixed << setprecision(10);
  // メイン
  ll N;
  cin >> N;
  vc<ll> A(N), B(N);
  rep(i, 0, N) cin >> A[i] >> B[i];

  int X = 50;
  Timer timer;
  Random_Gen rand1(0, 3), rand2(0, N-1), rand3(0, X-1), rand4(-2, 2);
  vc<ll> u(X, 0), v(X, 0);
  rep(i, 0, 50) u[i] = rand2(), v[i] = rand2();
  ll curscore = INF;
  while(timer.is_under(0.97)) {
    int sousa = rand1();
    vc<ll> nu(u), nv(v);
    
    if(sousa == 0) {
      int p = rand3(), add = rand4();
      nu[p] = max(0ll, min(N-1, u[p] + add));
    } else if(sousa == 1) {
      int p = rand3(), add = rand4();
      nv[p] = max(0ll, min(N-1, v[p] + add));
    } else if(sousa == 2) {
      int p1 = rand3(), p2 = rand3();
      swap(nu[p1], nu[p2]);
      swap(nv[p1], nv[p2]);
    }

    rep(i, 0, 50) {
      while(nu[i] == nv[i]) nu[i] = rand2();
    }
    if(chmin(curscore, score(A, B, nu, nv))) {
      u = nu, v = nv;
    }
  }
  cout << u.size() << endl;
  rep(i, 0, u.size()) {
    cout << u[i]+1 << " " << v[i]+1 << endl;
  }

  return 0;
}
0