結果
| 問題 | No.5020 Averaging |
| ユーザー |
 シャド
|
| 提出日時 | 2024-02-25 23:01:44 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 954 ms / 1,000 ms |
| コード長 | 6,905 bytes |
| コンパイル時間 | 4,570 ms |
| コンパイル使用メモリ | 288,788 KB |
| 実行使用メモリ | 6,548 KB |
| スコア | 40,589,675 |
| 最終ジャッジ日時 | 2024-02-25 23:02:41 |
| 合計ジャッジ時間 | 55,031 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge11 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| 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));}lli calcScore(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 calcScore(v[0].first, v[0].second);}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(v[0].first, v[0].second);lli nowLoopCount = 0;while (true) {nowLoopCount++;// if (nowLoopCount % 10000) {// cerr << nowScore << endl;// }endTime = std::chrono::system_clock::now();double elapsed =std::chrono::duration_cast<std::chrono::milliseconds>(endTime - start).count();if (elapsed > 950) {break;}//変更する答えの箇所を1つ選ぶint a = engine() % (opeCount-1);//変更する箇所にて、カード2つを適当に選択するint b = engine() % N;int c = engine() % N;int d = engine() % N;while (b == c) {c = engine() % N;}while (b == d || c == d) {d = engine() % N;}int preFirst = ans[a].first;int preSecond = ans[a].second;int preFirst2 = ans[a+1].first;int preSecond2 = ans[a+1].second;ans[a].first = b;ans[a].second = c;ans[a+1].first = c;ans[a+1].second = d;lli nextScore = calcScore(ans, baseV);if (nowScore <= nextScore) {nowScore = nextScore;v = baseV;} else {ans[a].first = preFirst;ans[a].second = preSecond;ans[a+1].first = preFirst2;ans[a+1].second = preSecond2;}}cerr << "loopCount = " << nowLoopCount << endl;cerr << "ansScore = " << nowScore << endl;cout << ans.size() << endl;for (auto e : ans) {cout << e.first + 1 << " " << e.second + 1 << endl;}}};int main() {start = std::chrono::system_clock::now();//まずは適当に50個選ぶSolver solver;return 0;}