結果
| 問題 | No.5020 Averaging |
| ユーザー |
 monnu
|
| 提出日時 | 2024-02-25 15:06:34 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 956 ms / 1,000 ms |
| コード長 | 5,745 bytes |
| コンパイル時間 | 2,280 ms |
| コンパイル使用メモリ | 179,936 KB |
| 実行使用メモリ | 6,676 KB |
| スコア | 15,298,769 |
| 最終ジャッジ日時 | 2024-02-25 15:07:26 |
| 合計ジャッジ時間 | 51,097 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge13 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:192:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
192 | for (auto [u, v] : ans)
| ^
main.cpp:57:37: warning: 'score' may be used uninitialized [-Wmaybe-uninitialized]
57 | double score = log10(max<ll>(1, score));
| ~~~~~~~^~~~~~~~~~
main.cpp:57:16: note: 'score' was declared here
57 | double score = log10(max<ll>(1, score));
| ^~~~~
ソースコード
#include <bits/stdc++.h>#include <random>using namespace std;using ll = long long;#define TARGET (500000000000000000)random_device seed_gen;mt19937 engine(seed_gen());uniform_real_distribution<> uniform_distribution(0.0, 1.0);double getRandomValue(){return uniform_distribution(engine);}int main(){int N;cin >> N;vector<ll> A(N), B(N);for (int i = 0; i < N; i++){cin >> A[i] >> B[i];}vector<int> contribution(N, -1);contribution[0] = 0;for (int i = 1; i < N; i++){int j = getRandomValue() * i;contribution[j]++;contribution[i] = contribution[j];}ll sumA = 0;ll sumB = 0;for (int i = 0; i < N; i++){sumA += A[i] / (1LL << (contribution[i]));sumB += B[i] / (1LL << (contribution[i]));}clock_t start = clock();double T_init = 1.0e2;double T_end = 1.0e-5;double limit = 0.9;while (true){clock_t end = clock();double elapsed = (double)(end - start) / CLOCKS_PER_SEC;if (elapsed > limit){break;}double T = T_init * pow(T_end / T_init, elapsed / limit);ll tmp = max(abs(sumA - TARGET), abs(sumB - TARGET));double score = log10(max<ll>(1, score));if (false && getRandomValue() < 0.3){// addvector<int> in, out;for (int i = 0; i < N; i++){if (contribution[i] == -1){out.push_back(i);}else{in.push_back(i);}}int i = getRandomValue() * out.size();i = out[i];int j = getRandomValue() * in.size();j = in[j];sumA -= A[j] / (1LL << contribution[j]);sumB -= B[j] / (1LL << contribution[j]);contribution[j]++;contribution[i] = contribution[j];sumA += A[j] / (1LL << contribution[j]);sumB += B[j] / (1LL << contribution[j]);sumA += A[i] / (1LL << contribution[i]);sumB += B[i] / (1LL << contribution[i]);ll tmp = max(abs(sumA - TARGET), abs(sumB - TARGET));double score_tmp = log10(max<ll>(1, score));if (score_tmp > score){sumA -= A[j] / (1LL << contribution[j]);sumB -= B[j] / (1LL << contribution[j]);sumA -= A[i] / (1LL << contribution[i]);sumB -= B[i] / (1LL << contribution[i]);contribution[j]--;contribution[i] = 0;sumA += A[j] / (1LL << contribution[j]);sumB += B[j] / (1LL << contribution[j]);}}else if (false && getRandomValue() < 0.5){// deletevector<int> in;for (int i = 1; i < N; i++){if (contribution[i] != -1){in.push_back(i);}}if (in.size() == 0){continue;}int i = getRandomValue() * in.size();i = in[i];vector<int> same;for (int j = 0; j < N; j++){if (i == j){continue;}if (contribution[i] == contribution[j]){same.push_back(j);}}if (same.size() == 0){continue;}}else{int i = getRandomValue() * N;int j = getRandomValue() * N;if (contribution[i] == contribution[j]){continue;}sumA -= A[i] / (1LL << contribution[i]);sumB -= B[i] / (1LL << contribution[i]);sumA -= A[j] / (1LL << contribution[j]);sumB -= B[j] / (1LL << contribution[j]);swap(contribution[i], contribution[j]);sumA += A[i] / (1LL << contribution[i]);sumB += B[i] / (1LL << contribution[i]);sumA += A[j] / (1LL << contribution[j]);sumB += B[j] / (1LL << contribution[j]);ll score_tmp = max(abs(sumA - TARGET), abs(sumB - TARGET));double diff = score - score_tmp;if (exp(diff / T) >= getRandomValue()){sumA -= A[i] / (1LL << contribution[i]);sumB -= B[i] / (1LL << contribution[i]);sumA -= A[j] / (1LL << contribution[j]);sumB -= B[j] / (1LL << contribution[j]);swap(contribution[i], contribution[j]);sumA += A[i] / (1LL << contribution[i]);sumB += B[i] / (1LL << contribution[i]);sumA += A[j] / (1LL << contribution[j]);sumB += B[j] / (1LL << contribution[j]);}}}vector<pair<int, int>> ans;priority_queue<pair<int, int>> pq;for (int i = 0; i < N; i++){pq.push({contribution[i], i});}while (pq.size() > 1){int u = pq.top().second;int d1 = pq.top().first;pq.pop();int v = pq.top().second;int d = pq.top().first;pq.pop();if (u > v){swap(u, v);}ans.push_back({u, v});pq.push({d - 1, u});}cout << ans.size() << '\n';for (auto [u, v] : ans){cout << u + 1 << ' ' << v + 1 << '\n';}}