結果
問題 | No.5020 Averaging |
ユーザー |
![]() |
提出日時 | 2024-02-20 17:26:04 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 861 ms / 1,000 ms |
コード長 | 2,155 bytes |
コンパイル時間 | 843 ms |
コンパイル使用メモリ | 79,416 KB |
実行使用メモリ | 6,548 KB |
スコア | 82,049,176 |
最終ジャッジ日時 | 2024-02-25 12:47:13 |
合計ジャッジ時間 | 46,537 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
// [想定解答 4-2] // - 山登り法を焼きなまし法に変える. // - 焼きなましの温度を適切に調整する.(調整しなければ点数が大幅に下がる) // - 80% 程度の得点が得られる. #include <iostream> #include <cmath> #include <ctime> #include <vector> #include <algorithm> using namespace std; const long long Target = 500000000000000000LL; long long N; long long A[59], C[59]; long long B[59], D[59]; long long Order[59]; long long BestOrder[59]; long long GetScore() { for (int i = 1; i <= N; i++) C[i] = A[i]; for (int i = 1; i <= N; i++) D[i] = B[i]; for (int i = 1; i <= N - 1; i++) { long long avgC = (C[Order[1]] + C[Order[i + 1]]) / 2LL; long long avgD = (D[Order[1]] + D[Order[i + 1]]) / 2LL; C[Order[1]] = avgC; C[Order[i + 1]] = avgC; D[Order[1]] = avgD; D[Order[i + 1]] = avgD; } return max(abs(Target - C[1]), abs(Target - D[1])); } long double Randouble() { double s = 0.0, t = 1.0; for (int i = 0; i < 3; i++) { t /= 1024.0; s += 1.0 * (rand() % 1024) * t; } return s; } int main() { // Step 1. 入力 cin >> N; for (int i = 1; i <= N; i++) cin >> A[i] >> B[i]; // Step 2. 山登り法 for (int i = 1; i <= N; i++) Order[i] = i; long long CurrentScore = GetScore(); long long BestScore = CurrentScore; int StartTime = clock(); while (clock() - StartTime <= 85 * CLOCKS_PER_SEC / 100) { int idx1 = rand() % (N - 1) + 2; int idx2 = rand() % (N - 1) + 2; swap(Order[idx1], Order[idx2]); long long CandScore = GetScore(); double Diff = log10(CurrentScore) - log10(CandScore); if (Randouble() < exp(Diff / 0.2)) { if (BestScore > CandScore) { BestScore = CandScore; for (int i = 1; i <= N; i++) BestOrder[i] = Order[i]; } CurrentScore = CandScore; } else { swap(Order[idx1], Order[idx2]); } } // Step 3. 答えを得る vector<pair<int, int>> Answer; for (int i = 1; i <= N - 1; i++) Answer.push_back(make_pair(BestOrder[1], BestOrder[i + 1])); // Step 4. 出力 cout << Answer.size() << endl; for (int i = 0; i < Answer.size(); i++) cout << Answer[i].first << " " << Answer[i].second << endl; return 0; }