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

• 問題: No.5020 Averaging
• ユーザー: takumi152
• 提出日時: 2024-02-25 16:41:22
• 言語: C++17(gcc12) (gcc 12.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 993 ms / 1,000 ms
• コード長: 14,971 bytes
• コンパイル時間: 4,785 ms
• コンパイル使用メモリ: 290,936 KB
• 実行使用メモリ: 6,548 KB
• スコア: 88,972,736
• 最終ジャッジ日時: 2024-02-25 16:43:01
• 合計ジャッジ時間: 57,116 ms
• ジャッジサーバーID （参考情報）: judge11 / judge12

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

ソースコード

#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);
      shuffle(merge_order.begin(), merge_order.end(), theMersenne);
      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;
      }
      
      Card result_card = cards[merge_order[0]];
      for (int i = 1; i < input.card_num; i++) {
        const int idx = merge_order[i];
        result_card.front = (result_card.front + cards[idx].front) / 2;
        result_card.back = (result_card.back + cards[idx].back) / 2;
      }

      score = max(abs(result_card.front - Const::target_value), abs(result_card.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;
    }
  };

  ll global_best_score = (ll) 9e18;
  Output global_best_output;
  for (int t = 0; t < 10; t++) {
    SAState state(input);
    {
      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 = 2e1;
      const double target_temperature = 5e0;
      // const double decay_rate = 4e-5;
      double temperature = base_temperature;

      int iter_count = 0;
      double time_start = theTimer.time();
      const double time_limit = (double) (t + 1) * 0.099;

      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 % 10000 == 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 % 10000 == 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 < 0.9) {
          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 % 10000 == 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;
          }
        }
        else if (roll < 0.95) {
          const int i1 = theRandom.nextUIntMod(Const::turn_max - input.card_num + 1);
          const int i2 = theRandom.nextUIntMod(Const::turn_max - input.card_num + 1);
          if (i1 == i2) continue;

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

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

          #ifdef DEBUG
          if (iter_count % 10000 == 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.pre_merge_order[i1], state.pre_merge_order[i2]);
            score = last_score;
          }
        }
        else if (roll < 1.0) {
          const int i1 = theRandom.nextUIntMod(Const::turn_max - input.card_num + 1);
          const int i2 = theRandom.nextUIntMod(Const::turn_max - input.card_num + 1);
          if (i1 == i2) continue;

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

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

          #ifdef DEBUG
          if (iter_count % 10000 == 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.erase(state.pre_merge_order.begin() + i2);
            state.pre_merge_order.insert(state.pre_merge_order.begin() + i1, orig_c);
            score = last_score;
          }
        }

        // temperature *= 1.0 - decay_rate;
        temperature = (double) best_score * 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();
      if (score < global_best_score) {
        global_best_score = score;
        global_best_output = state.get_output();
      }
    }
  }

  cerr << "global_best_score = " << global_best_score << endl;
  cerr << "raw_score         = " << (int) (2e6 - 1e5 * log10(global_best_score + 1)) << endl;

  return global_best_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;
}