結果
| 問題 |
No.5020 Averaging
|
| コンテスト | |
| ユーザー |
 takumi152
|
| 提出日時 | 2024-02-25 14:11:47 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 903 ms / 1,000 ms |
| コード長 | 9,432 bytes |
| コンパイル時間 | 3,748 ms |
| コンパイル使用メモリ | 271,344 KB |
| 実行使用メモリ | 6,676 KB |
| スコア | 14,097,316 |
| 最終ジャッジ日時 | 2024-02-25 14:12:40 |
| 合計ジャッジ時間 | 51,691 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;
};
// 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> merge_order;
ll score;
SAState(const Input& input): input(input) {
merge_order = vector<int>(input.card_num);
iota(merge_order.begin(), merge_order.end(), 0);
update_score_full();
}
void update_score_full() {
Card result_card;
for (int i = 0; i < input.card_num; i++) {
const Card& next_card = input.cards[merge_order[i]];
result_card.front += next_card.front << min(i + 1, input.card_num - 1);
result_card.back += next_card.back << min(i + 1, input.card_num - 1);
}
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;
int smallest_idx = merge_order[input.card_num - 1];
for (int i = input.card_num - 2; i >= 0; i--) {
int next_idx = merge_order[i];
output.merge_order.push_back(make_pair(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_merge_order = state.merge_order;
const double base_temperature = 1e19;
const double target_temperature = 1e16;
// 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.5) {
const int c1 = theRandom.nextUIntMod(input.card_num);
const int c2 = theRandom.nextUIntMod(input.card_num);
if (c1 == c2) continue;
swap(state.merge_order[c1], state.merge_order[c2]);
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_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[c1], state.merge_order[c2]);
score = last_score;
}
}
else if (roll < 1.0) {
const int c1 = theRandom.nextUIntMod(input.card_num);
const int c2 = theRandom.nextUIntMod(input.card_num);
if (c1 == c2) continue;
const int orig_c = state.merge_order[c1];
state.merge_order.erase(state.merge_order.begin() + c1);
state.merge_order.insert(state.merge_order.begin() + c2, 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_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() + c2);
state.merge_order.insert(state.merge_order.begin() + c1, 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.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;
}