結果
| 問題 | No.5020 Averaging |
| ユーザー |
 soto800
|
| 提出日時 | 2024-02-25 17:41:58 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 954 ms / 1,000 ms |
| コード長 | 7,818 bytes |
| コンパイル時間 | 4,705 ms |
| コンパイル使用メモリ | 291,496 KB |
| 実行使用メモリ | 6,676 KB |
| スコア | 36,865,876 |
| 最終ジャッジ日時 | 2024-02-25 17:42:54 |
| 合計ジャッジ時間 | 55,236 ms |
|
ジャッジサーバーID （参考情報） |
judge10 / judge15 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
#pragma GCC optimize("O3,O2")#pragma GCC optimize("unroll-loops")#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")#include <bits/stdc++.h>using namespace std;#define lli long long int#define REP(i, s, n) for (lli i = s; i < n; i++)#define INF (1LL << 62)#define mp(a, b) make_pair(a, b)#define SORT(V) sort(V.begin(), V.end())#define PI (3.141592653589794)#define TO_STRING(VariableName) #VariableName#define LOG1(x) \if (DEBUG) \cout << "#" << TO_STRING(x) << "=" << x << " " << endl;#define LOG2(x, y) \if (DEBUG) \cout << "#" << TO_STRING(x) << "=" << x << " " << TO_STRING(y) << "=" << y \<< endl;#define LOG3(x, y, z) \if (DEBUG) \cout << "#" << TO_STRING(x) << "=" << x << " " << TO_STRING(y) << "=" << y \<< " " << TO_STRING(z) << "=" << z << endl;#define LOG4(w, x, y, z) \if (DEBUG) \cout << "#" << TO_STRING(w) << "=" << w << " " << TO_STRING(x) << "=" << x \<< " " << TO_STRING(y) << "=" << y << " " << TO_STRING(z) << "=" << z \<< endl;#define LOG5(w, x, y, z, a) \if (DEBUG) \cout << "#" << TO_STRING(w) << "=" << w << " " << TO_STRING(x) << "=" << x \<< " " << TO_STRING(y) << "=" << y << " " << TO_STRING(z) << "=" << z \<< " " << TO_STRING(a) << "=" << a << endl;#define LOG6(w, x, y, z, a, b) \if (DEBUG) \cout << "#" << TO_STRING(w) << "=" << w << " " << TO_STRING(x) << "=" << x \<< " " << TO_STRING(y) << "=" << y << " " << TO_STRING(z) << "=" << z \<< " " << TO_STRING(a) << "=" << a << " " << TO_STRING(b) << "=" << b \<< endl;#define overload6(a, b, c, d, e, f, g, ...) g#define LOG(...) \overload6(__VA_ARGS__, LOG6, LOG5, LOG4, LOG3, LOG2, LOG1)(__VA_ARGS__)template <class T> bool chmax(T &a, const T &b) {if (a < b) {a = b;return 1;}return 0;}template <class T> bool chmin(T &a, const T &b) {if (b < a) {a = b;return 1;}return 0;}uint64_t rand64() {static uint64_t x = 88172645463325252ULL;x = x ^ (x << 7);return x = x ^ (x >> 9);}double rand_p() { return rand64() * (1.0 / UINT64_MAX); }#define LOCAL#define DEBUG 0#define UP 0#define RIGHT 1#define DOWN 2#define LEFT 3std::chrono::system_clock::time_point start, endTime;class Solver {private:lli N;vector<pair<lli, lli>> v;vector<pair<lli, lli>> baseV;mt19937 engine;lli calcScore(lli a, lli b) {lli v1 = abs(500000000000000000LL - a);lli v2 = abs(500000000000000000LL - b);return (2000000 - 100000 * log10(max(v1, v2) + 1));}vector<pair<lli, lli>> createCards(const vector<pair<int, int>> &ans,const vector<pair<lli, lli>> &baseV) {auto v = baseV;REP(i, 0, ans.size()) {lli a = ans[i].first;lli b = ans[i].second;lli firstAve = (v[a].first + v[b].first) / 2;lli secondAve = (v[a].second + v[b].second) / 2;v[a].first = firstAve;v[b].first = firstAve;v[a].second = secondAve;v[b].second = secondAve;}return move(v);}lli calcRealScore(const vector<pair<int, int>> &ans,const vector<pair<lli, lli>> &baseV) {auto v = createCards(ans, baseV);return calcScore(v[0].first, v[0].second);}lli calcScore(const vector<pair<int, int>> &ans,const vector<pair<lli, lli>> &baseV) {// auto v = createCards(ans, baseV);// lli allScore = 0;// for (lli i = 0; i < 3; i++) {// allScore += (10 - i * 3) * calcScore(v[i].first, v[i].second);// }// return allScore;return calcRealScore(ans, baseV);}public:Solver() {cin >> N;v.resize(N);REP(i, 0, N) { cin >> v[i].first >> v[i].second; }baseV = v;engine = mt19937(chrono::steady_clock::now().time_since_epoch().count());vector<pair<int, int>> ans;const int opeCount = 50;int loopCount = 0;// 50回答えを出すまでやるwhile (ans.size() < opeCount) {//無限ループ防止if (loopCount > 500) {break;}int a = 0;int b = engine() % N;while (a == b) {b = engine() % N;}//カードに次書く数字平均とスコアを計算する。lli firstAve = (v[a].first + v[b].first) / 2;lli secondAve = (v[a].second + v[b].second) / 2;lli nowScore = calcScore(v[0].first, v[0].second);lli nextScore = calcScore(firstAve, secondAve);LOG(nowScore, nextScore);//今のスコアのほうが高ければやり直しif (nowScore > nextScore) {loopCount++;continue;}//カードの更新v[a].first = firstAve;v[a].second = secondAve;v[b].first = firstAve;v[b].second = secondAve;ans.push_back(mp(a, b));loopCount = 0;}//初期解ができたら、それを元にして、ランダムに変更していくlli nowScore = calcScore(ans, baseV);lli nowLoopCount = 0;lli bestScore = nowScore;vector<pair<int, int>> bestAns = ans;while (true) {nowLoopCount++;endTime = std::chrono::system_clock::now();double elapsed =std::chrono::duration_cast<std::chrono::milliseconds>(endTime - start).count();const double finishElapsedMilisec = 950;if (elapsed > finishElapsedMilisec) {break;}static const long double start_temp = 1e2;static const long double end_temp = 1e0;long double temperature =exp(log(start_temp) -((log(start_temp) - log(end_temp)) *((elapsed / 1000.0) * (1.0 / (finishElapsedMilisec / 1000.0)))));//変更する答えの箇所を1つ選ぶint a = engine() % opeCount;//変更する箇所にて、カード2つを適当に選択するint b = engine() % N;int c = engine() % N;while (b == c) {c = engine() % N;}int preFirst = ans[a].first;int preSecond = ans[a].second;ans[a].first = b;ans[a].second = c;lli nextScore = calcScore(ans, baseV);lli diffScore = nextScore - nowScore;long double prob = std::exp(diffScore / temperature);LOG(prob, nowScore, nextScore);if (diffScore >= 0 || prob > rand_p()) {// if (diffScore >= 0) {nowScore = nextScore;v = baseV;} else {ans[a].first = preFirst;ans[a].second = preSecond;}if (bestScore < nextScore) {bestScore = nextScore;bestAns = ans;}}cerr << "loopCount = " << nowLoopCount << endl;cerr << "ansScore = " << calcRealScore(ans, baseV) << endl;cout << bestAns.size() << endl;for (auto e : bestAns) {cout << e.first + 1 << " " << e.second + 1 << endl;}}};int main() {start = std::chrono::system_clock::now();//まずは適当に50個選ぶSolver solver;return 0;}