#955909 (C++17) No.5020 Averaging

提出ソース

結果

問題	No.5020 Averaging
ユーザー	titan23
提出日時	2024-02-25 23:47:07
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	993 ms / 1,000 ms
コード長	5,173 bytes
コンパイル時間	3,618 ms
コンパイル使用メモリ	226,188 KB
実行使用メモリ	6,548 KB
スコア	81,434,854
最終ジャッジ日時	2024-02-25 23:48:03
合計ジャッジ時間	55,740 ms
ジャッジサーバーID （参考情報）	judge12 / judge15
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	992 ms 6,548 KB
testcase_01	AC	993 ms 6,548 KB
testcase_02	AC	992 ms 6,548 KB
testcase_03	AC	992 ms 6,548 KB
testcase_04	AC	992 ms 6,548 KB
testcase_05	AC	991 ms 6,548 KB
testcase_06	AC	992 ms 6,548 KB
testcase_07	AC	993 ms 6,548 KB
testcase_08	AC	992 ms 6,548 KB
testcase_09	AC	992 ms 6,548 KB
testcase_10	AC	993 ms 6,548 KB
testcase_11	AC	992 ms 6,548 KB
testcase_12	AC	992 ms 6,548 KB
testcase_13	AC	992 ms 6,548 KB
testcase_14	AC	992 ms 6,548 KB
testcase_15	AC	993 ms 6,548 KB
testcase_16	AC	992 ms 6,548 KB
testcase_17	AC	991 ms 6,548 KB
testcase_18	AC	991 ms 6,548 KB
testcase_19	AC	992 ms 6,548 KB
testcase_20	AC	992 ms 6,548 KB
testcase_21	AC	992 ms 6,548 KB
testcase_22	AC	993 ms 6,548 KB
testcase_23	AC	992 ms 6,548 KB
testcase_24	AC	993 ms 6,548 KB
testcase_25	AC	992 ms 6,548 KB
testcase_26	AC	992 ms 6,548 KB
testcase_27	AC	991 ms 6,548 KB
testcase_28	AC	992 ms 6,548 KB
testcase_29	AC	992 ms 6,548 KB
testcase_30	AC	993 ms 6,548 KB
testcase_31	AC	992 ms 6,548 KB
testcase_32	AC	991 ms 6,548 KB
testcase_33	AC	993 ms 6,548 KB
testcase_34	AC	992 ms 6,548 KB
testcase_35	AC	992 ms 6,548 KB
testcase_36	AC	992 ms 6,548 KB
testcase_37	AC	992 ms 6,548 KB
testcase_38	AC	992 ms 6,548 KB
testcase_39	AC	992 ms 6,548 KB
testcase_40	AC	993 ms 6,548 KB
testcase_41	AC	992 ms 6,548 KB
testcase_42	AC	992 ms 6,548 KB
testcase_43	AC	992 ms 6,548 KB
testcase_44	AC	992 ms 6,548 KB
testcase_45	AC	993 ms 6,548 KB
testcase_46	AC	992 ms 6,548 KB
testcase_47	AC	992 ms 6,548 KB
testcase_48	AC	992 ms 6,548 KB
testcase_49	AC	992 ms 6,548 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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 = 2e18;

const double TIME_LIMIT = 990;
const long long VAL = 5e17;

const int 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 {

   private:
    unsigned int _x, _y, _z, _w;

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

   public:
    Random() : _x(123456789),
               _y(362436069),
               _z(521288629),
               _w(88675123) {}

    double random() { return (double)(_xor128()) / 0xFFFFFFFF; }
    int randint(const int end) { return (((unsigned long long)_xor128() * (end+1)) >> 32); }
    int randint(const int begin, const int end) { return begin + (((unsigned long long)_xor128() * (end-begin+1)) >> 32); }
    int randrange(const int end) { return (((unsigned long long)_xor128() * end) >> 32); }
    int randrange(const int begin, const int end) { return begin + (((unsigned long long)_xor128() * (end-begin)) >> 32); }
  };
} // 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 = pair<int, int>;

  struct State {
    double score;
    vector<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 int &v: op) {
        a[0] = (a[0]+a[v])/2;
        b[0] = (b[0]+b[v])/2;
      }
      score = log(max(abs(VAL-a[0]), abs(VAL-b[0])));
    }

    double get_score() const { return score; }

    Changed modify() {
      double prob = myrandom.random();
      int indx1 = myrandom.randrange(op.size());
      int indx2 = myrandom.randrange(op.size());
      swap(op[indx1], op[indx2]);
      calc_score();
      return {indx1, indx2};
    }

    void rollback(Changed &changed) {
      swap(op[changed.first], op[changed.second]);
    }
  };

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

    double START_TEMP = 1;
    double END_TEMP   = 0.01;
    double TEMP_VAL = (START_TEMP - END_TEMP) / TIME_LIMIT;

    auto make_ans_init = [&] () -> State {
      State state;
      for (int u = 1; u < N; ++u) {
        state.op.emplace_back(u);
      }
      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);
      }
    }
    cerr << "cnt=" << cnt << endl;

    {
      ll a[N], b[N];
      rep(i, N) {
        a[i] = A[i];
        b[i] = B[i];
      }
      for (const int &v: best_ans.op) {
        ll x = (a[0]+a[v])/2;
        a[0] = x;
        a[v] = x;
        ll y = (b[0]+b[v])/2;
        b[0] = 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 (const int &v: ans.op) {
    cout << 1 << ' ' << v+1 << endl;
  }
}

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

yukicoder

結果

テストケース

ソースコード