結果
| 問題 |
No.5020 Averaging
|
| コンテスト | |
| ユーザー |
 neterukun
|
| 提出日時 | 2024-02-25 16:43:01 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 954 ms / 1,000 ms |
| コード長 | 6,287 bytes |
| コンパイル時間 | 2,171 ms |
| コンパイル使用メモリ | 179,728 KB |
| 実行使用メモリ | 6,676 KB |
| スコア | 41,148,794 |
| 最終ジャッジ日時 | 2024-02-25 16:45:59 |
| 合計ジャッジ時間 | 52,768 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge10 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| 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;
std::vector<long long> testA;
std::vector<long long> testB;
double rand;
int old_index, old_i, old_j;
int old_index0, old_index1, old_pattern, old_i0, old_j0, old_i1, old_j1;
State() {
REP(k, M) {
int i = rand64() % N;
int j = rand64() % N;
operations.emplace_back(i, j);
}
testA.resize(N);
testB.resize(N);
}
void modify() {
rand = rand_p();
if (rand < 0.2) {
int index = rand64() % M;
int i = rand64() % (N + 25);
int j = rand64() % (N + 25);
if (i >= N) i = 0;
if (j >= N) j = 0;
old_index = index;
old_i = operations[index].first;
old_j = operations[index].second;
operations[index] = std::make_pair(i, j);
} else {
int index0 = rand64() % M;
int index1 = rand64() % M;
old_pattern = rand64() % 4;
old_index0 = index0;
old_index1 = index1;
if (old_pattern == 0)
std::swap(operations[index0].first, operations[index1].first);
else if (old_pattern == 1)
std::swap(operations[index0].first, operations[index1].second);
else if (old_pattern == 2)
std::swap(operations[index0].second, operations[index1].first);
else if (old_pattern == 3)
std::swap(operations[index0].second, operations[index1].second);
}
}
void rollback() {
if (rand < 0.2) {
operations[old_index] = std::make_pair(old_i, old_j);
} else {
if (old_pattern == 0)
std::swap(operations[old_index0].first, operations[old_index1].first);
else if (old_pattern == 1)
std::swap(operations[old_index0].first, operations[old_index1].second);
else if (old_pattern == 2)
std::swap(operations[old_index0].second, operations[old_index1].first);
else if (old_pattern == 3)
std::swap(operations[old_index0].second, operations[old_index1].second);
}
}
long long calc_score() {
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));
// long long Score = -max(ErrorA, ErrorB);
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 = 1e4;
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) {
if (iter_count & 1024) {
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); // pow
inv_temp = 1.0 / temp;
}
cur_state.modify();
long long new_score = cur_state.calc_score();
double prob = std::exp((new_score - cur_score) * inv_temp);
if (prob > rand_p()) {
cur_score = new_score;
} else {
cur_state.rollback();
}
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;
}
int main() {
input();
Timer timer;
State state;
state = annealing(state, timer, 0.95);
std::cerr << state.calc_score() << std::endl;
state.print();
}