結果
| 問題 | No.5020 Averaging |
| コンテスト | |
| ユーザー |
 momohara
|
| 提出日時 | 2024-02-25 16:22:44 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 903 ms / 1,000 ms |
| コード長 | 6,406 bytes |
| コンパイル時間 | 5,237 ms |
| コンパイル使用メモリ | 317,968 KB |
| 実行使用メモリ | 6,548 KB |
| スコア | 14,463,416 |
| 最終ジャッジ日時 | 2024-02-25 16:23:42 |
| 合計ジャッジ時間 | 53,007 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge11 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
#include <atcoder/all>
#include <bits/stdc++.h>
#include <sys/time.h>
using namespace std;
using namespace atcoder;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using P = pair<ll, ll>;
using tp = tuple<ll, ll, ll>;
template <class T>
using vec = vector<T>;
template <class T>
using vvec = vector<vec<T>>;
#define all(hoge) (hoge).begin(), (hoge).end()
#define en '\n'
#define rep(i, m, n) for(ll i = (ll)(m); i < (ll)(n); ++i)
#define rep2(i, m, n) for(ll i = (ll)(n)-1; i >= (ll)(m); --i)
#define REP(i, n) rep(i, 0, n)
#define REP2(i, n) rep2(i, 0, n)
constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
// constexpr long long MOD = (ll)1e9 + 7;
constexpr long long MOD = 998244353LL;
static const ld pi = 3.141592653589793L;
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
template <class T>
inline bool chmin(T &a, T b) {
if(a > b) {
a = b;
return true;
}
return false;
}
template <class T>
inline bool chmax(T &a, T b) {
if(a < b) {
a = b;
return true;
}
return false;
}
constexpr double TL = 0.9;
struct Timer {
chrono::system_clock::time_point start, last_updated;
Timer() {
start = chrono::system_clock::now();
last_updated = chrono::system_clock::now();
}
void reset() {
start = chrono::system_clock::now();
}
void update() {
last_updated = chrono::system_clock::now();
}
double getTime() {
auto now = chrono::system_clock::now();
return chrono::duration<double>(now - start).count();
}
double should_finish_search1() {
return getTime() > TL;
}
bool should_reset() {
auto now = chrono::system_clock::now();
return chrono::duration<double>(now - last_updated).count() > 1.0 ||
chrono::duration<double>(now - start).count() > TL;
}
};
Timer timer;
struct Xor128 {
unsigned x, y, z, w;
Xor128() : x(123456789), y(362436069), z(521288629), w(88675123){};
inline unsigned xor128() {
unsigned t;
t = x ^ (x << 11);
x = y;
y = z;
z = w;
return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
int nextInt(int x, int y) {
return xor128() % (y - x) + x;
}
double nextDouble(double a, double b) {
return (double)(xor128() & 0xffff) / 0xffff * (b - a) + a;
}
};
auto rnd = Xor128();
void solve() {
timer = Timer();
// input
ll n;
cin >> n;
vec<ll> a(n), b(n);
REP(i, n) {
cin >> a[i] >> b[i];
}
// calc
ll base = (ll)5e17;
auto calc_score = [&](ll a0, ll b0, ll x) -> ll {
ll v1 = abs(a0 - base);
ll v2 = abs(b0 - base);
ll v = max(v1, v2);
ll score = 2000050 - x;
if(v)
score = 2000000 - 100000 * log10(v + 1);
return score;
};
auto play_score = [&](vec<P> &op, ll x) -> P {
auto aa = a;
auto bb = b;
ll max_score = calc_score(aa[0], bb[0], 0);
ll max_x = 0;
REP2(i, x) {
auto [u, v] = op[i];
ll na = (aa[u] + aa[v]) / 2;
ll nb = (bb[u] + bb[v]) / 2;
aa[u] = aa[v] = na;
bb[u] = bb[v] = nb;
ll score = calc_score(aa[0], bb[0], i + 1);
if(chmax(max_score, score)) {
max_x = i + 1;
}
}
return {max_score, max_x};
};
ll ma_score = calc_score(a[0], b[0], 0);
vec<P> ma_op;
ll ma_x = 0;
ll th = 12;
auto dfs = [&](auto &&self, vec<P> &op, vec<int> &updated, vec<int> &cand) -> void {
if(op.size() >= th or timer.should_finish_search1())
return;
REP(ii, cand.size()) {
REP(j, n) {
int i = cand[ii];
if(i == j or updated[i] == j and updated[j] == i)
continue;
// oparation
if(updated[j] == -1)
cand.push_back(j);
int pi = updated[i];
updated[i] = j;
int pj = updated[j];
updated[j] = i;
op.push_back({i, j});
// playout
auto [score, x] = play_score(op, op.size());
if(chmax(ma_score, score)) {
ma_op = op;
ma_x = x;
}
// dfs
self(self, op, updated, cand);
// rollback
op.pop_back();
updated[i] = pi;
updated[j] = pj;
if(updated[j] == -1)
cand.pop_back();
}
}
};
// 深さthまで全探索
{
vec<P> op;
vector updated(n, -1);
vector cand({0});
dfs(dfs, op, updated, cand);
}
// // ランダムに操作を作成
// do {
// vec<P> op(50);
// vector updated(n, -1);
// vector cand({0});
// REP(i, 50) {
// int r1 = cand[rnd.nextInt(0, cand.size())];
// int r2 = rnd.nextInt(0, n - 1);
// if(r2 >= r1)
// r2++;
// while(updated[r1] == r2 and updated[r2] == r1) {
// // 同じ操作を2回連続は避ける
// r2 = rnd.nextInt(0, n - 1);
// if(r2 >= r1)
// r2++;
// }
// if(updated[r2] == -1)
// cand.push_back(r2);
// updated[r1] = r2;
// updated[r2] = r1;
// op[i] = {r1, r2};
// }
// // playout
// auto [score, x] = play_score(op, op.size());
// if(chmax(ma_score, score)) {
// ma_op = op;
// ma_x = x;
// }
// } while(!timer.should_finish_search1());
// output
cout << ma_x << en;
REP(i, ma_x) {
auto [u, v] = ma_op[i];
cout << u + 1 << " " << v + 1 << en;
}
#if !defined(ONLINE_JUDGE)
// ローカル用出力
// cerr << timer.getTime() << en;
cerr << ma_score << en;
#endif
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// cout << fixed << setprecision(10);
// ll t;
// cin >> t;
// REP(i, t - 1) {
// solve();
// }
solve();
return 0;
}