結果
問題 | No.5020 Averaging |
ユーザー |
![]() |
提出日時 | 2024-02-25 13:44:34 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 953 ms / 1,000 ms |
コード長 | 5,740 bytes |
コンパイル時間 | 2,135 ms |
コンパイル使用メモリ | 175,880 KB |
実行使用メモリ | 6,676 KB |
スコア | 33,879,592 |
最終ジャッジ日時 | 2024-02-25 13:45:27 |
合計ジャッジ時間 | 52,647 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <chrono>#include <cmath>#include <cstdint>#include <cstring>#include <deque>#include <iostream>#include <map>#include <memory>#include <queue>#include <random>#include <set>#include <string>#include <unordered_map>#include <unordered_set>#include <vector>using namespace std;#define REP(i, n) for (int i = 0; i < (int)(n); ++ (i))#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))uint64_t rand64() {static uint64_t x = 88172645463325252ULL;x = x ^ (x << 7);return x = x ^ (x >> 9);}double rand_p() { return rand64() * (1.0 / UINT64_MAX); }using namespace std::chrono;using namespace std;struct Timer {system_clock::time_point start;Timer() { reset(); }void reset() { start = system_clock::now(); }double sec_elapsed() const {return duration_cast<milliseconds>(system_clock::now() - start).count() / 1000.0;}};constexpr int N = 45;constexpr int M = 50;long long A[N];long long B[N];void input() {int tmp;std::cin >> tmp;REP(i, N) {std::cin >> A[i] >> B[i];}}struct State {std::vector<std::pair<int, int>> operations;State() {REP(k, M) {int i = rand64() % N;int j = rand64() % N;operations.emplace_back(i, j);}}void modify() {int index = rand64() % M;int i = rand64() % N;int j = rand64() % N;operations[index] = std::make_pair(i, j);}void modify(int index, int i, int j) {operations[index] = std::make_pair(i, j);}long long calc_score() {std::vector<long long> testA(N);std::vector<long long> testB(N);REP(i, N) {testA[i] = A[i];testB[i] = B[i];}for (auto &op : operations) {int i = op.first;int j = op.second;long long avgA = (testA[i] + testA[j]) / 2LL;long long avgB = (testB[i] + testB[j]) / 2LL;testA[i] = avgA;testA[j] = avgA;testB[i] = avgB;testB[j] = avgB;}long long ErrorA = abs(500000000000000000LL - testA[0]);long long ErrorB = abs(500000000000000000LL - testB[0]);long long Score = (long long)(2000000.0L - 100000.0L * log10(1.0L * max(ErrorA, ErrorB) + 1.0L));return Score;}void print() {int invalid_count = 0;REP(i, M) {int a = operations[i].first;int b = operations[i].second;if (a == b) {invalid_count += 1;}}std::cout << M - invalid_count << std::endl;REP(i, M) {int a = operations[i].first;int b = operations[i].second;if (a != b) {std::cout << a + 1<< " " << b + 1 << std::endl;}}}};State annealing(State cur_state, const Timer &timer, const double time_limit) {// 温度設定const double start_temp = 1e8;const double end_temp = 1e0;double inv_temp = 1.0 / start_temp;int iter_count = 0;long long cur_score = cur_state.calc_score();State best_state = cur_state;long long best_score = best_state.calc_score();double start_time = timer.sec_elapsed();double now = start_time;while (now < time_limit) {{now = timer.sec_elapsed();const double time_ratio = (now - start_time) / (time_limit - start_time);// const double temp = start_temp + (end_temp - start_temp) * time_ratio; // 線形const double temp = start_temp * std::pow(end_temp / start_temp, time_ratio); // powinv_temp = 1.0 / temp;}State new_state = cur_state;new_state.modify();long long new_score = new_state.calc_score();double prob = std::exp((new_score - cur_score) * inv_temp);if (prob > rand_p()) {cur_state = std::move(new_state);cur_score = new_score;}if (cur_score > best_score) {best_score = cur_score;best_state = cur_state;}iter_count += 1;}std::cerr << iter_count << std::endl;return best_state;}State kick(State cur_state, const Timer &timer, const double time_limit) {int iter_count = 0;long long cur_score = cur_state.calc_score();State best_state = cur_state;long long best_score = best_state.calc_score();double start_time = timer.sec_elapsed();double now = start_time;while (now < time_limit) {now = timer.sec_elapsed();bool update = false;REP(index, M) REP(i, N) REP3(j, i + 1, N) {State new_state = cur_state;long long new_score = new_state.calc_score();new_state.modify(index, i, j);if (cur_score > best_score) {cur_state = new_state;cur_score = new_score;update = true;}}if (cur_score > best_score) {best_score = cur_score;best_state = cur_state;}if (!update) {// kickするstd::cout << cur_score << std::endl;cur_state.modify();cur_score = cur_state.calc_score();}iter_count += 1;}std::cerr << iter_count << std::endl;return best_state;}int main() {input();Timer timer;State state;state = annealing(state, timer, 0.95);state.print();}