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

• 問題: No.5020 Averaging
• ユーザー: takumi152
• 提出日時: 2024-02-25 15:50:37
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 903 ms / 1,000 ms
• コード長: 11,884 bytes
• コンパイル時間: 4,758 ms
• コンパイル使用メモリ: 280,536 KB
• 実行使用メモリ: 6,676 KB
• スコア: 83,636,343
• 最終ジャッジ日時: 2024-02-25 15:51:46
• 合計ジャッジ時間: 51,990 ms
• ジャッジサーバーID （参考情報）: judge10 / judge13

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

ソースコード

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

#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <array>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <random>
#include <functional>
#include <memory>
#include <cmath>
#include <cassert>

#ifdef _MSC_VER
#include <intrin.h>
#else
#include <x86intrin.h>
#endif

struct xorshift64 {
  unsigned long long int x = 88172645463325252ULL;
  inline unsigned short nextUShort() {
    x = x ^ (x << 7);
    return x = x ^ (x >> 9);
  }
  inline unsigned int nextUShortMod(unsigned long long int mod) {
    x = x ^ (x << 7);
    x = x ^ (x >> 9);
    return ((x & 0x0000ffffffffffff) * mod) >> 48;
  }
  inline unsigned int nextUInt() {
    x = x ^ (x << 7);
    return x = x ^ (x >> 9);
  }
  inline unsigned int nextUIntMod(unsigned long long int mod) {
    x = x ^ (x << 7);
    x = x ^ (x >> 9);
    return ((x & 0x00000000ffffffff) * mod) >> 32;
  }
  inline unsigned long long int nextULL() {
    x = x ^ (x << 7);
    return x = x ^ (x >> 9);
  }
  inline double nextDouble() {
    x = x ^ (x << 7);
    x = x ^ (x >> 9);
    return (double)x * 5.42101086242752217e-20;
  }
};

struct timer {
  double t = 0.0;
  double lastStop = 0.0;
  bool stopped = false;
  timer() {
    restart();
  }
  inline void restart() {
    t = now();
    stopped = false;
  }
  inline void start() {
    if (stopped) {
      t += now() - lastStop;
      stopped = false;
    }
  }
  inline void stop() {
    if (!stopped) {
      lastStop = now();
      stopped = true;
    }
  }
  inline double time() {
    if (stopped) return lastStop - t;
    else return now() - t;
  }
  inline double now() {
    #ifdef _MSC_VER
      #ifdef LOCAL
        return __rdtsc() * 2.857142857142857e-10; // 1 / 3.5e9, for local (Ryzen 9 3950X)
      #else
        //return __rdtsc() * 3.5714285714285715e-10; // 1 / 2.8e9, for AWS EC2 C3 (Xeon E5-2680 v2)
        //return __rdtsc() * 3.4482758620689656e-10; // 1 / 2.9e9, for AWS EC2 C4 (Xeon E5-2666 v3)
        //return __rdtsc() * 3.333333333333333e-10; // 1 / 3.0e9, for AWS EC2 C5 (Xeon Platinum 8124M / Xeon Platinum 8275CL)
        // return __rdtsc() * 3.4482758620689656e-10; // 1 / 2.9e9, for AWS EC2 C6i (Xeon Platinum 8375C)
        return __rdtsc() * 4.3478260869565215e-10; // 1 / 2.3e9, for yukicoder judge
      #endif
    #else
      unsigned long long l, h;
        __asm__ ("rdtsc" : "=a"(l), "=d"(h));
      #ifdef LOCAL
        return (double)(l | h << 32) * 2.857142857142857e-10; // 1 / 3.5e9, for local (Ryzen 9 3950X)
      #else
        //return (double)(l | h << 32) * 3.5714285714285715e-10; // 1 / 2.8e9, for AWS EC2 C3 (Xeon E5-2680 v2)
        //return (double)(l | h << 32) * 3.4482758620689656e-10; // 1 / 2.9e9, for AWS EC2 C4 (Xeon E5-2666 v3)
        //return (double)(l | h << 32) * 3.333333333333333e-10; // 1 / 3.0e9, for AWS EC2 C5 (Xeon Platinum 8124M / Xeon Platinum 8275CL)
        // return (double)(l | h << 32) * 3.4482758620689656e-10; // 1 / 2.9e9, for AWS EC2 C6i (Xeon Platinum 8375C)
        return (double)(l | h << 32) * 4.3478260869565215e-10; // 1 / 2.3e9, for yukicoder judge
      #endif
    #endif
  }
};

using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<int, int> Pii;
typedef unsigned char uchar;

const ll mod = 1000000007;

timer theTimer;
xorshift64 theRandom;
mt19937_64 theMersenne(1);

// libraries
namespace Lib {
}

// hyper parameters
namespace HyperParameter {
  void load_hyper_parameter(int argc, char *argv[]) {
    // do nothing
  }
}

// enums

// structs
struct Card {
  ll front, back;
  Card(): front(0), back(0) {}
  Card(ll front, ll back): front(front), back(back) {}
};

// constants
struct Const {
  static constexpr ll target_value = (ll) 5e17;
  static constexpr int turn_max = 50;
};

// inputs
struct Input {
  int card_num;
  vector<Card> cards;
};

// outputs
struct Output {
  vector<pair<int, int>> merge_order;
};

// internals

Input get_input() {
  Input input;

  cin >> input.card_num;
  input.cards.resize(input.card_num);
  for (int i = 0; i < input.card_num; i++) {
    cin >> input.cards[i].front >> input.cards[i].back;
  }

  return input;
}

void init(Input& input) {
  // do nothing
}

Output solve(const Input& input) {
  struct SAState {
    const Input& input;
    vector<int> pre_merge_order;
    vector<int> merge_order;

    ll score;

    SAState(const Input& input): input(input) {
      pre_merge_order = vector<int>(Const::turn_max - input.card_num + 1);
      merge_order = vector<int>(input.card_num);
      iota(merge_order.begin(), merge_order.end(), 0);
      update_score_full();
    }

    void update_score_full() {
      static vector<Card> cards(input.card_num);
      for (int i = 0; i < input.card_num; i++) cards[i] = input.cards[i];

      for (int i = 0; i < Const::turn_max - input.card_num; i++) {
        const int idx1 = merge_order[pre_merge_order[i]];
        const int idx2 = merge_order[pre_merge_order[i + 1]];
        const ll front = (cards[idx1].front + cards[idx2].front) / 2;
        const ll back = (cards[idx1].back + cards[idx2].back) / 2;
        cards[idx1].front = front;
        cards[idx1].back = back;
        cards[idx2].front = front;
        cards[idx2].back = back;
      }
      
      int smallest_idx = merge_order[0];
      for (int i = 1; i < input.card_num; i++) {
        const int idx1 = merge_order[i];
        const int idx2 = smallest_idx;
        const ll front = (cards[idx1].front + cards[idx2].front) / 2;
        const ll back = (cards[idx1].back + cards[idx2].back) / 2;
        cards[idx1].front = front;
        cards[idx1].back = back;
        cards[idx2].front = front;
        cards[idx2].back = back;
        smallest_idx = min(smallest_idx, idx1);
      }

      score = max(abs(cards[0].front - Const::target_value), abs(cards[0].back - Const::target_value));
    }

    ll get_score() {
      return score;
    }

    Output get_output() {
      Output output;

      for (int i = 0; i < Const::turn_max - input.card_num; i++) {
        if (pre_merge_order[i] != pre_merge_order[i + 1]) {
          output.merge_order.emplace_back(merge_order[pre_merge_order[i]], merge_order[pre_merge_order[i + 1]]);
        }
      }

      int smallest_idx = merge_order[0];
      for (int i = 1; i < input.card_num; i++) {
        int next_idx = merge_order[i];
        output.merge_order.emplace_back(smallest_idx, next_idx);
        if (next_idx < smallest_idx) {
          smallest_idx = next_idx;
        }
      }
      return output;
    }
  };

  SAState state(input);
  Output output;
  {
    ll score = state.get_score();
    ll last_score = score;
    ll best_score = score;
    vector<int> best_pre_merge_order = state.pre_merge_order;
    vector<int> best_merge_order = state.merge_order;

    const double base_temperature = 1e19;
    const double target_temperature = 1e0;
    // const double decay_rate = 4e-5;
    double temperature = base_temperature;

    int iter_count = 0;
    double time_start = theTimer.time();
    const double time_limit = 0.900;

    while (true) {
      if (iter_count % 1024 == 0 && theTimer.time() > time_limit) break;
      const double roll = theRandom.nextDouble();
      if (roll < 0.4) {
        const int i1 = theRandom.nextUIntMod(input.card_num);
        const int i2 = theRandom.nextUIntMod(input.card_num);
        if (i1 == i2) continue;

        swap(state.merge_order[i1], state.merge_order[i2]);

        state.update_score_full();
        score = state.get_score();

        #ifdef DEBUG
        if (iter_count % 100000 == 0) cerr << iter_count << " " << score << " " << last_score << " " << best_score << " " << temperature << " " << theTimer.time() << endl;
        #endif

        if (score <= last_score) {
          last_score = score;
          if (score < best_score) {
            best_score = score;
            best_pre_merge_order = state.pre_merge_order;
            best_merge_order = state.merge_order;
          }
        }
        else if (theRandom.nextDouble() < exp(double(last_score - score) / temperature)) { // accept
          last_score = score;
        }
        else { // rollback
          swap(state.merge_order[i1], state.merge_order[i2]);
          score = last_score;
        }
      }
      else if (roll < 0.8) {
        const int i1 = theRandom.nextUIntMod(input.card_num);
        const int i2 = theRandom.nextUIntMod(input.card_num);
        if (i1 == i2) continue;

        const int orig_c = state.merge_order[i1];
        state.merge_order.erase(state.merge_order.begin() + i1);
        state.merge_order.insert(state.merge_order.begin() + i2, orig_c);

        state.update_score_full();
        score = state.get_score();

        #ifdef DEBUG
        if (iter_count % 100000 == 0) cerr << iter_count << " " << score << " " << last_score << " " << best_score << " " << temperature << " " << theTimer.time() << endl;
        #endif

        if (score <= last_score) {
          last_score = score;
          if (score < best_score) {
            best_score = score;
            best_pre_merge_order = state.pre_merge_order;
            best_merge_order = state.merge_order;
          }
        }
        else if (theRandom.nextDouble() < exp(double(last_score - score) / temperature)) { // accept
          last_score = score;
        }
        else { // rollback
          state.merge_order.erase(state.merge_order.begin() + i2);
          state.merge_order.insert(state.merge_order.begin() + i1, orig_c);
          score = last_score;
        }
      }
      else if (roll < 1.0) {
        const int i = theRandom.nextUIntMod(Const::turn_max - input.card_num + 1);
        const int c = theRandom.nextUIntMod(5);

        const int orig_c = state.pre_merge_order[i];
        state.pre_merge_order[i] = c;

        state.update_score_full();
        score = state.get_score();

        #ifdef DEBUG
        if (iter_count % 100000 == 0) cerr << iter_count << " " << score << " " << last_score << " " << best_score << " " << temperature << " " << theTimer.time() << endl;
        #endif

        if (score <= last_score) {
          last_score = score;
          if (score < best_score) {
            best_score = score;
            best_pre_merge_order = state.pre_merge_order;
            best_merge_order = state.merge_order;
          }
        }
        else if (theRandom.nextDouble() < exp(double(last_score - score) / temperature)) { // accept
          last_score = score;
        }
        else { // rollback
          state.pre_merge_order[i] = orig_c;
          score = last_score;
        }
      }

      // temperature *= 1.0 - decay_rate;
      temperature = exp(log(base_temperature) - ((log(base_temperature) - log(target_temperature)) * ((theTimer.time() - time_start) * (1.0 / (time_limit - time_start)))));
      iter_count++;
    }

    cerr << "iter_count  = " << iter_count << endl;
    cerr << "last_score  = " << last_score << endl;
    cerr << "best_score  = " << best_score << endl;
    cerr << "temperature = " << temperature << endl;

    state.pre_merge_order = best_pre_merge_order;
    state.merge_order = best_merge_order;
    state.update_score_full();
  }

  return state.get_output();
}

void print_output(const Output& output) {
  cout << output.merge_order.size() << endl;
  for (auto p: output.merge_order) {
    cout << p.first + 1 << " " << p.second + 1 << endl;
  }
}

int main(int argc, char *argv[]) {
  cin.tie(0);
  ios::sync_with_stdio(false);

  HyperParameter::load_hyper_parameter(argc, argv);

  auto input = get_input();

  init(input);

  auto output = solve(input);

  print_output(output);

  return 0;
}