結果
問題 | No.5020 Averaging |
ユーザー |
![]() |
提出日時 | 2024-02-25 13:45:32 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 1,000 ms |
コード長 | 1,533 bytes |
コンパイル時間 | 5,756 ms |
コンパイル使用メモリ | 313,240 KB |
実行使用メモリ | 6,676 KB |
スコア | 18,794,206 |
最終ジャッジ日時 | 2024-02-25 13:45:41 |
合計ジャッジ時間 | 8,135 ms |
ジャッジサーバーID (参考情報) |
judge10 / judge11 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
#include <bits/stdc++.h>using namespace std;using namespace chrono;#if __has_include(<atcoder/all>)#include <atcoder/all>using namespace atcoder;#endifint main() {int64_t n;cin >> n;vector<int64_t> as_64(n), bs_64(n);for (int64_t i = 0; i < n; i++) {cin >> as_64[i] >> bs_64[i];}vector<__int128_t> as(n), bs(n);for (int64_t i = 0; i < n; i++) {as[i] = as_64[i];bs[i] = bs_64[i];}__int128_t c = 500000000000000000LL;vector<int64_t> us, vs;for (int64_t t = 0; t < 50; t++) {int64_t u = -1, v = -1;for (int64_t i = 0; i < n; i++) {for (int64_t j = i + 1; j < n; j++) {if ((as[i] < c) != (as[j] < c) && (bs[i] < c) != (bs[j] < c)) {if (u == -1 ||((as[i] - c) + (as[j] - c)) * ((as[i] - c) + (as[j] - c)) +((bs[i] - c) + (bs[j] - c)) *((bs[i] - c) + (bs[j] - c)) <((as[u] - c) + (as[v] - c)) * ((as[u] - c) + (as[v] - c)) +((bs[u] - c) + (bs[v] - c)) *((bs[u] - c) + (bs[v] - c))) {u = i;v = j;}}}}if (u != -1) {int64_t x = (as[u] + as[v]) / 2;int64_t y = (bs[u] + bs[v]) / 2;as[u] = as[v] = x;bs[u] = bs[v] = y;us.push_back(u + 1);vs.push_back(v + 1);}}cout << us.size() << endl;for (int64_t i = 0; i < us.size(); i++) {cout << us[i] << ' ' << vs[i] << endl;}return 0;}