結果
問題 | No.5020 Averaging |
ユーザー | e869120 |
提出日時 | 2024-02-23 15:56:28 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 841 ms / 1,000 ms |
コード長 | 10,436 bytes |
コンパイル時間 | 6,833 ms |
コンパイル使用メモリ | 118,292 KB |
実行使用メモリ | 220,916 KB |
スコア | 94,559,885 |
最終ジャッジ日時 | 2024-02-25 12:57:03 |
合計ジャッジ時間 | 40,283 ms |
ジャッジサーバーID (参考情報) |
judge10 / judge11 |
純コード判定しない問題か言語 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 432 ms
220,916 KB |
testcase_01 | AC | 827 ms
220,916 KB |
testcase_02 | AC | 828 ms
220,916 KB |
testcase_03 | AC | 827 ms
220,916 KB |
testcase_04 | AC | 827 ms
220,916 KB |
testcase_05 | AC | 827 ms
220,916 KB |
testcase_06 | AC | 825 ms
220,916 KB |
testcase_07 | AC | 827 ms
220,916 KB |
testcase_08 | AC | 552 ms
220,916 KB |
testcase_09 | AC | 386 ms
220,916 KB |
testcase_10 | AC | 827 ms
220,916 KB |
testcase_11 | AC | 667 ms
220,916 KB |
testcase_12 | AC | 541 ms
220,916 KB |
testcase_13 | AC | 542 ms
220,916 KB |
testcase_14 | AC | 814 ms
220,916 KB |
testcase_15 | AC | 827 ms
220,916 KB |
testcase_16 | AC | 826 ms
220,916 KB |
testcase_17 | AC | 828 ms
220,916 KB |
testcase_18 | AC | 569 ms
220,916 KB |
testcase_19 | AC | 773 ms
220,916 KB |
testcase_20 | AC | 636 ms
220,916 KB |
testcase_21 | AC | 630 ms
220,916 KB |
testcase_22 | AC | 455 ms
220,916 KB |
testcase_23 | AC | 581 ms
220,916 KB |
testcase_24 | AC | 827 ms
220,916 KB |
testcase_25 | AC | 718 ms
220,916 KB |
testcase_26 | AC | 827 ms
220,916 KB |
testcase_27 | AC | 826 ms
220,916 KB |
testcase_28 | AC | 431 ms
220,916 KB |
testcase_29 | AC | 744 ms
220,916 KB |
testcase_30 | AC | 485 ms
220,916 KB |
testcase_31 | AC | 826 ms
220,916 KB |
testcase_32 | AC | 826 ms
220,916 KB |
testcase_33 | AC | 447 ms
220,916 KB |
testcase_34 | AC | 428 ms
220,916 KB |
testcase_35 | AC | 827 ms
220,916 KB |
testcase_36 | AC | 826 ms
220,916 KB |
testcase_37 | AC | 451 ms
220,916 KB |
testcase_38 | AC | 663 ms
220,916 KB |
testcase_39 | AC | 680 ms
220,916 KB |
testcase_40 | AC | 826 ms
220,916 KB |
testcase_41 | AC | 781 ms
220,916 KB |
testcase_42 | AC | 826 ms
220,916 KB |
testcase_43 | AC | 470 ms
220,916 KB |
testcase_44 | AC | 827 ms
220,916 KB |
testcase_45 | AC | 675 ms
220,916 KB |
testcase_46 | AC | 841 ms
220,916 KB |
testcase_47 | AC | 827 ms
220,916 KB |
testcase_48 | AC | 796 ms
220,916 KB |
testcase_49 | AC | 827 ms
220,916 KB |
ソースコード
#include <iostream> #include <map> #include <cmath> #include <ctime> #include <tuple> #include <vector> #include <algorithm> using namespace std; const long long MaxVal = 1000000000000000000LL; const long long MinVal = 100000000000000000LL; const long long Target = 500000000000000000LL; long long N; long long A[59], LA[59]; long long B[59], LB[59]; long long FinalScore = MaxVal; vector<pair<int, int>> FinalAns; // 終盤探索用 vector<int> backtrack; vector<pair<vector<int>, int>> Possibility; map<long long, bool> Possibility_Record; int IndexCount = 0; int Masks[1 << 20]; long long MaximumA[1 << 19], MaximumB[1 << 19]; long long MinimumA[1 << 19], MinimumB[1 << 19]; int ListIndex[4000][2009]; int ListCount[4000][2009]; tuple<int, int, int> List[4000][2009]; tuple<int, int, int> ListTemp[4000][2009]; // ========================================================================================================== 初期解探索 void init_dfs(int depth, vector<long long> ArrayA) { for (int i = 0; i < 4; i++) { if (Possibility_Record[ArrayA[i]] == false) { Possibility_Record[ArrayA[i]] = true; backtrack.push_back(i + 1); int hash_val = 0; for (int j = 0; j < backtrack.size(); j++) hash_val += (backtrack[j] << (4 * j)); Possibility.push_back(make_pair(backtrack, hash_val)); backtrack.pop_back(); } } if (depth == 7) return; for (int i = 0; i < 4; i++) { for (int j = i + 1; j < 4; j++) { if (ArrayA[i] == ArrayA[j]) continue; vector<long long> ArrayC = ArrayA; long long avg1 = (ArrayC[i] + ArrayC[j]) / 2LL; ArrayC[i] = avg1; ArrayC[j] = avg1; backtrack.push_back(i + (j << 2)); init_dfs(depth + 1, ArrayC); backtrack.pop_back(); } } } void Initialize(int mask, vector<int> idx) { Masks[mask] = IndexCount; vector<long long> ArrayA(4, 0); vector<long long> ArrayB(4, 0); // Enumerate Part int cnt = 0; for (int i = 0; i < Possibility.size(); i++) { ArrayA[0] = A[idx[0]]; ArrayB[0] = B[idx[0]]; ArrayA[1] = A[idx[1]]; ArrayB[1] = B[idx[1]]; ArrayA[2] = A[idx[2]]; ArrayB[2] = B[idx[2]]; ArrayA[3] = A[idx[3]]; ArrayB[3] = B[idx[3]]; for (int j = 0; j < Possibility[i].first.size(); j++) { if (j + 1 == Possibility[i].first.size()) { int num = Possibility[i].first[j] - 1; ListIndex[IndexCount][(ArrayA[num] >> 49) + 1]++; ListTemp[IndexCount][cnt] = make_tuple(ArrayB[num] >> 41, ArrayA[num] >> 41, Possibility[i].second); cnt += 1; } else { int idxA = (Possibility[i].first[j] & 3); int idxB = (Possibility[i].first[j] >> 2); long long avgA = (ArrayA[idxA] + ArrayA[idxB]) >> 1; long long avgB = (ArrayB[idxA] + ArrayB[idxB]) >> 1; ArrayA[idxA] = avgA; ArrayB[idxA] = avgB; ArrayA[idxB] = avgA; ArrayB[idxB] = avgB; } } } // Add Part for (int i = 1; i <= 2000; i++) ListIndex[IndexCount][i] += ListIndex[IndexCount][i - 1]; for (int i = 0; i <= 2000; i++) ListCount[IndexCount][i] = ListIndex[IndexCount][i]; for (int i = 0; i < cnt; i++) { int idx = get<1>(ListTemp[IndexCount][i]) >> 8; List[IndexCount][ListCount[IndexCount][idx]] = ListTemp[IndexCount][i]; ListCount[IndexCount][idx]++; } } // ========================================================================================================== 基本関数 long long GetScore(vector<int>& Order) { long long TotalScore1 = (A[1] >> (N - 1)); long long TotalScore2 = (B[1] >> (N - 1)); for (int i = 0; i < N - 1; i++) TotalScore1 += (A[Order[i]] >> (N - 1 - i)); for (int i = 0; i < N - 1; i++) TotalScore2 += (B[Order[i]] >> (N - 1 - i)); return max(abs(Target - TotalScore1), abs(Target - TotalScore2)); } long long GetActual(vector<pair<int, int>>& Operation) { for (int i = 1; i <= N; i++) LA[i] = A[i]; for (int i = 1; i <= N; i++) LB[i] = B[i]; for (int i = 0; i < Operation.size(); i++) { int idx1 = Operation[i].first; int idx2 = Operation[i].second; long long avgA = (LA[idx1] + LA[idx2]) / 2LL; long long avgB = (LB[idx1] + LB[idx2]) / 2LL; LA[idx1] = avgA; LA[idx2] = avgA; LB[idx1] = avgB; LB[idx2] = avgB; } long long gosa = max(abs(Target - LA[1]), abs(Target - LB[1])); return gosa; } 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; } // ========================================================================================================== 序盤・中盤探索 vector<int> GetBestOrder() { vector<int> Order(N - 1, 0); vector<int> BestOrder(N - 1, 0); for (int i = 0; i < N - 1; i++) Order[i] = i + 2; // 準備 long long CurrentScore = GetScore(Order); long long BestScore = CurrentScore; int StartTime = clock(); // 焼きなまし法開始 while (clock() - StartTime <= 10 * CLOCKS_PER_SEC / 100) { int idx1 = rand() % (N - 1); int idx2 = rand() % (N - 1); swap(Order[idx1], Order[idx2]); long long CandScore = GetScore(Order); double Diff = log10(CurrentScore) - log10(CandScore); if (Randouble() < exp(Diff / 0.17)) { if (BestScore > CandScore) { BestScore = CandScore; BestOrder = Order; } CurrentScore = CandScore; } else { swap(Order[idx1], Order[idx2]); } } return BestOrder; } // ========================================================================================================== 終盤探索 vector<int> CurrentOrder; int StartTime; int NumLoops; void dfs(int depth, int mask, long long CurrentA, long long CurrentB, vector<int>& Cand, vector<int>& PostOrder) { if ((NumLoops & 1023) == 0) { if (clock() - StartTime > 80 * CLOCKS_PER_SEC / 100) return; } NumLoops += 1; if (depth == 4) { int idx = Masks[(1 << Cand.size()) - 1 - mask]; int Remain = max(0LL, min(1999LL, (Target - CurrentA) / 256LL)); for (int pos = ListIndex[idx][Remain]; pos < ListIndex[idx][Remain + 1]; pos++) { long long gosaA = abs(Target - (CurrentA + 1LL * get<1>(List[idx][pos]))); long long gosaB = abs(Target - (CurrentB + 1LL * get<0>(List[idx][pos]))); if (max(gosaA, gosaB) > FinalScore + 100LL) continue; // 手順の計算 vector<int> MaskOrd; vector<pair<int, int>> Final; for (int i = 0; i < Cand.size(); i++) { if (!((mask >> i) & 1)) MaskOrd.push_back(Cand[i]); } for (int i = 0; i < 8; i++) { int val1 = (get<2>(List[idx][pos]) >> (4 * i)) & 15; int val2 = (get<2>(List[idx][pos]) >> (4 * i + 4)) & 15; if (val2 == 0) { Final.push_back(make_pair(1, MaskOrd[val1 - 1])); for (int j = CurrentOrder.size() - 1; j >= 0; j--) Final.push_back(make_pair(1, CurrentOrder[j])); for (int j = 0; j < PostOrder.size(); j++) Final.push_back(make_pair(1, PostOrder[j])); break; } else Final.push_back(make_pair(MaskOrd[val1 & 3], MaskOrd[val1 >> 2])); } // スコアの計算 long long Score = GetActual(Final); if (FinalScore > Score) { FinalScore = Score; FinalAns = Final; } } return; } // 枝刈り探索 int dep = PostOrder.size() + CurrentOrder.size() + 1; int cur = (1 << Cand.size()) - 1 - mask; for (int i = 0; i < Cand.size(); i++) { if ((mask >> i) & 1) continue; long long NextA = CurrentA + (A[Cand[i]] >> dep); long long NextB = CurrentB + (B[Cand[i]] >> dep); if (NextA < Target - MaximumA[cur - (1 << i)] || NextA > Target - MinimumA[cur - (1 << i)]) continue; if (NextB < Target - MaximumB[cur - (1 << i)] || NextB > Target - MinimumB[cur - (1 << i)]) continue; CurrentOrder.push_back(Cand[i]); dfs(depth - 1, mask + (1 << i), NextA, NextB, Cand, PostOrder); CurrentOrder.pop_back(); } } int main() { // Step 1. 入力 cin >> N; for (int i = 1; i <= N; i++) cin >> A[i] >> B[i]; // Step 2. 初期化 vector<long long> Random(4, 0); Random[0] = 123456789123456789; Random[1] = 314159265358979323; Random[2] = 869120869120869120; Random[3] = 999999999999999999; init_dfs(0, Random); // Step 3. 焼きなまし法 StartTime = clock(); vector<int> BestOrder = GetBestOrder(); // Step 4. 終盤探索 (初期化) for (int i = 0; i < 18; i++) { for (int j = i + 1; j < 18; j++) { for (int k = j + 1; k < 18; k++) { for (int l = k + 1; l < 18; l++) { Initialize((1 << i) + (1 << j) + (1 << k) + (1 << l), vector<int>{BestOrder[i], BestOrder[j], BestOrder[k], BestOrder[l]}); IndexCount += 1; } } } } vector<pair<long long, int>> SortedA; vector<pair<long long, int>> SortedB; for (int i = 0; i < 18; i++) SortedA.push_back(make_pair(A[BestOrder[i]], i)); for (int i = 0; i < 18; i++) SortedB.push_back(make_pair(B[BestOrder[i]], i)); sort(SortedA.begin(), SortedA.end()); sort(SortedB.begin(), SortedB.end()); for (int i = 0; i < (1 << 18); i++) { int cntA = 0; int cntB = 0; MinimumA[i] = -10000; MinimumA[i] = -10000; MaximumA[i] = 10000; MaximumB[i] = 10000; for (int j = 17; j >= 0; j--) { if ((i >> SortedA[j].second) & 1) { if (cntA <= 3) MinimumA[i] = (SortedA[j].first >> 41); else MinimumA[i] += (SortedA[j].first >> (44 - cntA)); cntA += 1; } if ((i >> SortedB[j].second) & 1) { if (cntB <= 3) MinimumB[i] = (SortedB[j].first >> 41); else MinimumB[i] += (SortedB[j].first >> (44 - cntB)); cntB += 1; } } cntA = 0; cntB = 0; for (int j = 0; j <= 17; j++) { if ((i >> SortedA[j].second) & 1) { if (cntA <= 3) MaximumA[i] = (SortedA[j].first >> 41); else MaximumA[i] += (SortedA[j].first >> (44 - cntA)); cntA += 1; } if ((i >> SortedB[j].second) & 1) { if (cntB <= 3) MaximumB[i] = (SortedB[j].first >> 41); else MaximumB[i] += (SortedB[j].first >> (44 - cntB)); cntB += 1; } } } // Step 5. 終盤探索 for (int depth = 6; depth <= 18; depth++) { long long SumA = (A[1] >> (N - 4)); long long SumB = (B[1] >> (N - 4)); for (int i = depth; i < N - 1; i++) SumA += (A[BestOrder[i]] >> (N - 1 - i)); for (int i = depth; i < N - 1; i++) SumB += (B[BestOrder[i]] >> (N - 1 - i)); vector<int> Vec1; vector<int> Vec2; for (int i = 0; i < depth; i++) Vec1.push_back(BestOrder[i]); for (int i = depth; i < N - 1; i++) Vec2.push_back(BestOrder[i]); dfs(depth, 0, SumA, SumB, Vec1, Vec2); // printf("% 3d% 9lld% 9d% 7d\n", depth, min(99999999LL, FinalScore), NumLoops, clock() - StartTime); if (clock() - StartTime > 80 * CLOCKS_PER_SEC / 100) break; } // Step 6. 出力 cout << FinalAns.size() << endl; for (pair<int, int> ans : FinalAns) cout << ans.first << " " << ans.second << endl; return 0; }