結果
問題 |
No.5020 Averaging
|
ユーザー |
![]() |
提出日時 | 2024-02-25 14:31:01 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,827 bytes |
コンパイル時間 | 4,336 ms |
コンパイル使用メモリ | 285,320 KB |
実行使用メモリ | 6,676 KB |
スコア | 37,445,771 |
最終ジャッジ日時 | 2024-02-25 14:31:54 |
合計ジャッジ時間 | 52,374 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge10 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 44 TLE * 6 |
ソースコード
// #pragma GCC target("avx2") #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> // #include<sys/time.h> // #include<atcoder/segtree> using namespace std; // using mint = atcoder::modint998244353; const int M = 998244353; const long long LM = 1LL << 60; using P = pair<int, int>; pair<vector<P>, long long> solve(vector<long long> a, vector<long long> b, int L) { int n = a.size(); long long T = 500000000000000000LL; auto calc = [&](int i, int j) { return max(abs(a[i] + a[j] - T * 2), abs(b[i] + b[j] - T * 2)); }; vector<P> ans; auto op = [&](int i, int j) { if (i == j) return; if (ans.size() >= 50) return; ans.emplace_back(i, j); auto av = (a[i] + a[j]) / 2; auto bv = (b[i] + b[j]) / 2; a[i] = av; a[j] = av; b[i] = bv; b[j] = bv; }; // auto calc2 = [&](int i, int j) { // return abs(a[i] + a[j] - T * 2) + abs(b[i] + b[j] - T * 2); // }; while ((int)ans.size() < L) { int p = -1, q = -1; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (calc(i, j) < calc(i, i) && calc(i, j) < calc(j, j)) { if (p == -1 || calc(i, j) < calc(p, q)) { p = i; q = j; } } } } if (p == -1) break; op(p, q); } auto greedy = [&]() { while (ans.size() < 50) { int q = 0; for (int i = 1; i < n; ++i) { if (calc(0, q) > calc(0, i)) { q = i; } } if (q == 0) break; op(0, q); } }; auto orig_a = a; auto orig_b = b; auto orig_ans = ans; greedy(); auto best_ans = ans; auto best_score = calc(0, 0); for (int i = 1; i < n; ++i) { a = orig_a; b = orig_b; ans = orig_ans; op(0, i); greedy(); if (best_score > calc(0, 0)) { best_ans = ans; best_score = calc(0, 0); } } for (int i = 1; i < n; ++i) { for (int j = 1; j < n; ++j) { if (i == j) continue; a = orig_a; b = orig_b; ans = orig_ans; op(0, i); op(0, j); greedy(); if (best_score > calc(0, 0)) { best_ans = ans; best_score = calc(0, 0); } } } for (int i = 1; i < n; ++i) { for (int j = 1; j < n; ++j) { if (i == j) continue; for (int k = 1; k < n; ++k) { if (j == k) continue; a = orig_a; b = orig_b; ans = orig_ans; op(0, i); op(0, j); op(0, k); greedy(); if (best_score > calc(0, 0)) { best_ans = ans; best_score = calc(0, 0); } } } } ans = best_ans; return { ans, best_score }; } int main() { cin.tie(0); ios::sync_with_stdio(0); int n; cin >> n; vector<long long> a(n), b(n); for (int i = 0; i < n; ++i) { cin >> a[i] >> b[i]; } vector<P> ans; long long score = LM; for (int i = 5; i <= 40; i += 5) { auto res = solve(a, b, i); if (score > res.second) { ans = res.first; score = res.second; cerr << i << '\n'; } } if (ans.size() > 50) { ans.resize(50); } cout << ans.size() << '\n'; for (auto& i : ans) { cout << i.first + 1 << ' ' << i.second + 1 << '\n'; } return 0; }