結果
| 問題 | 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 3
std::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;
}