結果

問題 No.5020 Averaging
ユーザー titan23titan23
提出日時 2024-02-25 13:48:01
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 993 ms / 1,000 ms
コード長 6,628 bytes
コンパイル時間 5,007 ms
コンパイル使用メモリ 230,416 KB
実行使用メモリ 6,676 KB
スコア 39,272,314
最終ジャッジ日時 2024-02-25 13:48:59
合計ジャッジ時間 55,854 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 992 ms
6,676 KB
testcase_01 AC 992 ms
6,676 KB
testcase_02 AC 992 ms
6,676 KB
testcase_03 AC 993 ms
6,676 KB
testcase_04 AC 991 ms
6,676 KB
testcase_05 AC 992 ms
6,676 KB
testcase_06 AC 992 ms
6,676 KB
testcase_07 AC 991 ms
6,676 KB
testcase_08 AC 992 ms
6,676 KB
testcase_09 AC 992 ms
6,676 KB
testcase_10 AC 992 ms
6,676 KB
testcase_11 AC 993 ms
6,676 KB
testcase_12 AC 992 ms
6,676 KB
testcase_13 AC 992 ms
6,676 KB
testcase_14 AC 992 ms
6,676 KB
testcase_15 AC 992 ms
6,676 KB
testcase_16 AC 992 ms
6,676 KB
testcase_17 AC 992 ms
6,676 KB
testcase_18 AC 992 ms
6,676 KB
testcase_19 AC 992 ms
6,676 KB
testcase_20 AC 992 ms
6,676 KB
testcase_21 AC 992 ms
6,676 KB
testcase_22 AC 992 ms
6,676 KB
testcase_23 AC 992 ms
6,676 KB
testcase_24 AC 992 ms
6,676 KB
testcase_25 AC 993 ms
6,676 KB
testcase_26 AC 992 ms
6,676 KB
testcase_27 AC 992 ms
6,676 KB
testcase_28 AC 992 ms
6,676 KB
testcase_29 AC 993 ms
6,676 KB
testcase_30 AC 992 ms
6,676 KB
testcase_31 AC 992 ms
6,676 KB
testcase_32 AC 992 ms
6,676 KB
testcase_33 AC 992 ms
6,676 KB
testcase_34 AC 991 ms
6,676 KB
testcase_35 AC 992 ms
6,676 KB
testcase_36 AC 992 ms
6,676 KB
testcase_37 AC 992 ms
6,676 KB
testcase_38 AC 992 ms
6,676 KB
testcase_39 AC 992 ms
6,676 KB
testcase_40 AC 992 ms
6,676 KB
testcase_41 AC 992 ms
6,676 KB
testcase_42 AC 991 ms
6,676 KB
testcase_43 AC 992 ms
6,676 KB
testcase_44 AC 992 ms
6,676 KB
testcase_45 AC 992 ms
6,676 KB
testcase_46 AC 993 ms
6,676 KB
testcase_47 AC 992 ms
6,676 KB
testcase_48 AC 991 ms
6,676 KB
testcase_49 AC 992 ms
6,676 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <chrono>
using namespace std;

// #include <atcoder/all>
// using namespace atcoder;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define ll long long
static constexpr ll INF = 1e18;
static constexpr int inf = 1e9;

const double TIME_LIMIT = 990;
const long long VAL = 5e17;
const int OP_SIZE = 50;

const long long N = 45;
long long A[N];
long long B[N];

template<typename T>
T abs(const T &a, const T &b) { return a<b? b-a: a-b; }


// Random
namespace titan23 {

  struct Random {
    unsigned int _x, _y, _z, _w;

    Random() {
      _x = 123456789;
      _y = 362436069;
      _z = 521288629;
      _w = 88675123;
    }

    unsigned int _xor128() {
      unsigned int t = _x ^ (_x << 11);
      _x = _y;
      _y = _z;
      _z = _w;
      _w = (_w ^ (_w >> 19)) ^ (t ^ (t >> 8));
      return _w;
    }

    double random() {
      return (double)(_xor128()) / 0xFFFFFFFF;
    }

    int randint(int begin, int end) {
      assert(begin <= end);
      return begin + _xor128() % (end - begin + 1);
    }

    double randdouble(double begin, double end) {
      assert(begin < end);
      return begin + random() * (end-begin);
    }

    int randrange(int begin, int end) {
      assert(begin < end);
      return begin + _xor128() % (end - begin);
    }

    template <typename T>
    void shuffle(vector<T> &a) {
      int n = (int)a.size();
      for (int i = 0; i < n-1; ++i) {
        int j = randrange(i, n);
        swap(a[i], a[j]);
      }
    }

    template <typename T>
    T choice(const vector<T> &a) {
      int i = randrange(0, a.size());
      return a[i];
    }

    template <typename T>
    T choice(const vector<T> &a, const vector<int> &w, bool normal) {
      assert(normal == false);
      assert(a.size() == w.size());
      double sum = 0.0;
      for (const int &x: w) sum += x;
      assert(sum > 0);
      vector<double> x(w.size());
      for (int i = 0; i < x.size(); ++i) {
        x[i] = (double)w[i] / sum;
        if (i-1 >= 0) x[i] += x[i-1];
      }
      return choice(a, x);
    }

    template <typename T>
    T choice(const vector<T> &a, const vector<double> &w) {
      double i = random();
      int l = -1, r = a.size()-1;
      while (r - l > 1) {
        int mid = (l + r) / 2;
        if (w[mid] <= i) l = mid;
        else r = mid;
      }
      return a[r];
    }
  };
} // namespace titan23

titan23::Random myrandom;

// Timer
namespace titan23 {
  class Timer {
  public:
    Timer() : start_timepoint(std::chrono::high_resolution_clock::now()) {}

    void reset() {
      start_timepoint = std::chrono::high_resolution_clock::now();
    }

    double elapsed() {
      auto end_timepoint = std::chrono::high_resolution_clock::now();
      auto start = std::chrono::time_point_cast<std::chrono::microseconds>(start_timepoint).time_since_epoch().count();
      auto end = std::chrono::time_point_cast<std::chrono::microseconds>(end_timepoint).time_since_epoch().count();
      return (end - start) * 0.001; // ミリ秒単位で経過時間を返す
    }

  private:
    std::chrono::time_point<std::chrono::high_resolution_clock> start_timepoint;
  };
}

// SA 最小化
namespace titan23 {

namespace sa {

  titan23::Random sa_random;

  using Changed = vector<pair<int, int>>;

  struct State {
    double score;
    vector<pair<int, int>> op;

    State() : score(0.0) {}

    double get_score() const {
      ll a[N], b[N];
      rep(i, N) {
        a[i] = A[i];
        b[i] = B[i];
      }
      for (auto &[u, v]: op) {
        ll x = (a[u]+a[v])/2;
        a[u] = x;
        a[v] = x;
        ll y = (b[u]+b[v])/2;
        b[u] = y;
        b[v] = y;
      }
      return max(abs(VAL-a[0]), abs(VAL-b[0]));
    }

    Changed modify() {
      vector<pair<int, int>> pre_op = op;
      double prob = myrandom.random();
      if (op.empty() || (prob < 0.2 && op.size()+1 <= OP_SIZE)) {
        int indx = myrandom.randint(0, op.size());
        int u = myrandom.randrange(0, N);
        int v = myrandom.randrange(0, N);
        while (u == v) {
          v = myrandom.randrange(0, N);
        }
        pair<int, int> uv = {u, v};
        op.insert(op.begin()+indx, uv);
      } else if (prob < 0.4) {
        assert(!op.empty());
        int indx = myrandom.randrange(0, op.size());
        op.erase(op.begin() + indx);
      } else {
        int indx = myrandom.randrange(0, op.size());
        int u = myrandom.randrange(0, N);
        int v = myrandom.randrange(0, N);
        while (u == v) {
          v = myrandom.randrange(0, N);
        }
        pair<int, int> uv = {u, v};
        op[indx] = uv;
      }
      return pre_op;
    }

    void rollback(Changed &changed) {
      op = changed;
    }
  };

  // TIME_LIMIT: ms
  State run(const double TIME_LIMIT) {
    titan23::Timer sa_timer;

    double START_TEMP = 100.0;
    double END_TEMP = 1.0;
    double TEMP_VAL = (START_TEMP - END_TEMP) / TIME_LIMIT;

    auto make_ans_init = [&] () -> State {
      State state;
      return state;
    };

    State ans = make_ans_init();
    State best_ans = ans;
    double score = ans.get_score();
    double best_score = score;

    int cnt = 0;
    while (true) {
      double now_time = sa_timer.elapsed();
      if (now_time > TIME_LIMIT) break;
      ++cnt;
      Changed changed = ans.modify();
      double new_score = ans.get_score();
      double arg = score - new_score;
      if (arg >= 0 || exp(arg/(START_TEMP-TEMP_VAL*now_time)) > sa_random.random()) {
        score = new_score;
        if (score < best_score) {
          best_score = score;
          best_ans = ans;
        }
      } else {
        ans.rollback(changed);
      }
    }
    cerr << "cnt=" << cnt << endl;

    {
      ll a[N], b[N];
      rep(i, N) {
        a[i] = A[i];
        b[i] = B[i];
      }
      for (auto &[u, v]: best_ans.op) {
        ll x = (a[u]+a[v])/2;
        a[u] = x;
        a[v] = x;
        ll y = (b[u]+b[v])/2;
        b[u] = y;
        b[v] = y;
      }
      ll v1 = abs(VAL - a[0]);
      ll v2 = abs(VAL - b[0]);
      ll s = 2000000 - 100000*log10(max(v1, v2)+1);
      cerr << "score=" << s*50 / 1e8 << endl;
    }    
    return best_ans;
  }
}
}  // namespace titan23

using namespace titan23;

void solve() {
  int n_;
  cin >> n_;
  rep(i, N) cin >> A[i] >> B[i];

  sa::State ans = sa::run(TIME_LIMIT);

  cout << ans.op.size() << endl;
  for (auto &[u, v]: ans.op) {
    cout << u+1 << ' ' << v+1 << endl;
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  solve();
  return 0;
}
0