#955744 (C++17(gcc12)) No.5020 Averaging

• 問題: No.5020 Averaging
• ユーザー: titan23
• 提出日時: 2024-02-25 16:58:06
• 言語: C++17(gcc12) (gcc 12.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 996 ms / 1,000 ms
• コード長: 8,236 bytes
• コンパイル時間: 3,834 ms
• コンパイル使用メモリ: 235,596 KB
• 実行使用メモリ: 6,548 KB
• スコア: 43,088,208
• 最終ジャッジ日時: 2024-02-25 17:00:13
• 合計ジャッジ時間: 56,555 ms
• ジャッジサーバーID （参考情報）: judge15 / judge12

ファイルパターン	結果
other	AC * 50

ソースコード

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

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

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define ll long long
#define double float
static constexpr ll INF = 2e18;

static constexpr const double TIME_LIMIT = 993;
static constexpr const long long VAL = 5e17;
static constexpr const int OP_SIZE = 50;

static constexpr 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; }

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

template<typename T, typename S>
T min(const T &a, const S &b) { return a<b? 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(const int begin, const int end) {
      return begin + _xor128() % (end - begin + 1);
    }

    int randrange(const int begin, const int end) {
      return begin + _xor128() % (end - begin);
    }
  };
} // 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;

  struct Changed {
    double pre_score;
    int type;
    int indx;
    pair<int, int> uv;
    int indx1, indx2;
    Changed() {}
    Changed(double score) : pre_score(score) {}
  };

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

    State() : score(0.0) {}

    void calc_score() {
      ll a[N], b[N];
      memcpy(a, A, N * sizeof(ll));
      memcpy(b, B, N * sizeof(ll));
      for (const auto &[u, v]: op) {
        a[u] = a[v] = (a[u]+a[v])/2;
        b[u] = b[v] = (b[u]+b[v])/2;
      }
      score = log(max(abs(VAL-a[0]), abs(VAL-b[0])));
    }

    double get_score() { return score; }

    Changed modify() {
      Changed changed(score);
      double prob = myrandom.random();
      if (op.empty() || (prob < 0.1 && op.size()+1 <= OP_SIZE)) {
        changed.type = 0;
        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);
        changed.indx = indx;
      } else if (prob < 0.12) {
        changed.type = 1;
        int indx = myrandom.randrange(0, op.size());
        changed.indx = indx;
        changed.uv = op[indx];
        op.erase(op.begin() + indx);
      } else if (prob < 0.81) {
        changed.type = 10;
        {
          int indx = myrandom.randrange(0, op.size());
          changed.indx1 = indx;
          changed.uv = op[indx];
          op.erase(op.begin() + indx);
        }
        {
          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};
          changed.indx2 = indx;
          op.insert(op.begin()+indx, uv);
        }
      } else if (prob < 0.96) {
        changed.type = 2;
        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);
        }
        changed.indx = indx;
        changed.uv = op[indx];
        pair<int, int> uv = {u, v};
        op[indx] = uv;
      } else {
        changed.type = 3;
        int indx = myrandom.randrange(0, op.size());
        auto [pre_u, pre_v] = op[indx];
        int u = pre_u, v = pre_v;
        if (myrandom.random() < 0.4) {
          u = myrandom.randrange(0, N);
          while (u == pre_u || u == pre_v) {
            u = myrandom.randrange(0, N);
          }
        } else {
          v = myrandom.randrange(0, N);
          while (v == pre_v || v == pre_u) {
            v = myrandom.randrange(0, N);
          }
        }
        changed.indx = indx;
        changed.uv = op[indx];
        pair<int, int> uv = {u, v};
        op[indx] = uv;
      }
      calc_score();
      return changed;
    }

    void rollback(Changed &changed) {
      if (changed.type == 0) {
        op.erase(op.begin() + changed.indx);
      } else if (changed.type == 1) {
        op.insert(op.begin() + changed.indx, changed.uv);
      } else if (changed.type == 2) {
        op[changed.indx] = changed.uv;
      } else if (changed.type == 3) {
        op[changed.indx] = changed.uv;
      } else if (changed.type == 10) {
        op.erase(op.begin() + changed.indx2);
        op.insert(op.begin() + changed.indx1, changed.uv);
      }
      score = changed.pre_score;
    }
  };

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

    double START_TEMP = 0.0001;
    double END_TEMP   = 0.00001;
    double TEMP_VAL = (START_TEMP - END_TEMP) / TIME_LIMIT;

    auto make_ans_init = [&] () -> State {
      State state;
      ll a[N], b[N];
      memcpy(a, A, N * sizeof(ll));
      memcpy(b, B, N * sizeof(ll));
      rep(op_indx, 40) {
        if (op_indx % 2 == 0) { // to 0;
          vector<ll> delta(N, INF);
          ll mn = INF;
          for (int i = 1; i < N; ++i) {
            delta[i] = abs(VAL-(a[0]+a[i])/2) + abs(VAL-(b[0]+b[i])/2);
            if (delta[i] < mn) mn = delta[i];
          }
          for (int i = 1; i < N; ++i) {
            if (delta[i] == mn) {
              state.op.emplace_back(0, i);
              break;
            }
          }
        } else {
          pair<int, int> ans;
          ll best = INF;
          for (int i = 1; i < N; ++i) {
            for (int j = i+1; j < N; ++j) {
              ll this_s = abs(VAL - (a[0] + (a[i]+a[j])/2) / 2)
                        + abs(VAL - (b[0] + (b[i]+b[j])/2) / 2);
              if (this_s < best) {
                best = this_s;
                ans = {i, j};
              }
            }
          }
          state.op.push_back(ans);
        }
      }
      state.calc_score();
      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);
      }
    }
    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() << '\n';
  for (auto &[u, v]: ans.op) {
    cout << u+1 << ' ' << v+1 << '\n';
  }
}

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