結果
| 問題 |
No.5020 Averaging
|
| コンテスト | |
| ユーザー |
 titan23
|
| 提出日時 | 2024-02-25 17:10:52 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 993 ms / 1,000 ms |
| コード長 | 6,597 bytes |
| コンパイル時間 | 3,479 ms |
| コンパイル使用メモリ | 230,980 KB |
| 実行使用メモリ | 6,676 KB |
| スコア | 42,590,409 |
| 最終ジャッジ日時 | 2024-02-25 17:11:48 |
| 合計ジャッジ時間 | 55,939 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge10 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
#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
#define double float
static constexpr ll INF = 2e18;
const double TIME_LIMIT = 990;
const long long VAL = 5e17;
const int OP_SIZE = 50;
const long long 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; }
// print
namespace titan23 {
// pair<K, V>
template <typename K, typename V>
ostream& operator<<(ostream& os, const pair<K, V>& p) {
os << "(" << p.first << ", " << p.second << ")";
return os;
}
// vector<T>
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& a) {
int n = (int)a.size();
os << "[";
for (int i = 0; i < n-1; ++i) {
os << a[i] << ", ";
}
if (n > 0) {
os << a.back();
}
os << "]";
return os;
}
} // namespace titan23
using namespace titan23;
// Random
namespace titan23 {
struct Random {
unsigned int _x, _y, _z, _w;
Random() {
_x = 123456789;
_y = 362436069;
_z = 521288629;
_w = 88675123;
}
unsigned int _xor128() {
unsigned int t = _x ^ (_x << 11);
_x = _y;
_y = _z;
_z = _w;
_w = (_w ^ (_w >> 19)) ^ (t ^ (t >> 8));
return _w;
}
double random() {
return (double)(_xor128()) / 0xFFFFFFFF;
}
int randint(int begin, int end) {
return begin + _xor128() % (end - begin + 1);
}
int randrange(int begin, int end) {
return begin + _xor128() % (end - begin);
}
};
} // 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;
struct Changed {
double pre_score;
int type;
int indx;
pair<int, int> uv;
int indx1, indx2;
Changed() {}
Changed(double score) : pre_score(score) {}
};
struct State {
double score;
vector<pair<int, 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 auto &[u, v]: op) {
a[u] = a[v] = (a[u]+a[v])/2;
b[u] = b[v] = (b[u]+b[v])/2;
}
score = log(max(abs(VAL-a[0]), abs(VAL-b[0])));
}
double get_score() { return score; }
Changed modify() {
Changed changed(score);
double prob = myrandom.random();
if (prob < 0.4) {
changed.type = 0;
int indx1 = myrandom.randrange(0, op.size());
int indx2 = myrandom.randrange(0, op.size());
swap(op[indx1], op[indx2]);
changed.indx1 = indx1;
changed.indx2 = indx2;
} else {
changed.type = 1;
int indx = myrandom.randrange(0, op.size());
auto [pre_u, pre_v] = op[indx];
int v = myrandom.randrange(1, N);
while (v == pre_v) v = myrandom.randrange(1, N);
changed.indx = indx;
changed.uv = op[indx];
pair<int, int> uv = {0, v};
op[indx] = uv;
}
calc_score();
return changed;
}
void rollback(Changed &changed) {
if (changed.type == 0) {
swap(op[changed.indx1], op[changed.indx2]);
} else if (changed.type == 1) {
op[changed.indx] = changed.uv;
}
score = changed.pre_score;
}
};
// TIME_LIMIT: ms
State run(const double TIME_LIMIT) {
titan23::Timer sa_timer;
double START_TEMP = 10;
double END_TEMP = 0.1;
double TEMP_VAL = (START_TEMP - END_TEMP) / TIME_LIMIT;
auto make_ans_init = [&] () -> State {
State state;
ll a[N], b[N];
memcpy(a, A, N * sizeof(ll));
memcpy(b, B, N * sizeof(ll));
rep(op_indx, 50) {
int u = myrandom.randrange(1, N);
state.op.emplace_back(0, 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) cerr << arg << ' ' << exp(arg/(START_TEMP-TEMP_VAL*now_time)) << endl;
if (arg >= 0 || exp(arg/(START_TEMP-TEMP_VAL*now_time)) > sa_random.random()) {
score = new_score;
if (score < best_score) {
best_score = score;
cerr << best_score << endl;
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 (auto &[u, v]: best_ans.op) {
ll x = (a[u]+a[v])/2;
a[u] = x;
a[v] = x;
ll y = (b[u]+b[v])/2;
b[u] = 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 (auto &[u, v]: ans.op) {
cout << u+1 << ' ' << v+1 << endl;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
solve();
return 0;
}