#pragma GCC optimize("O3,O2") #pragma GCC optimize("unroll-loops") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx") #include 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 bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } template 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> v; vector> 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> createCards(const vector> &ans, const vector> &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> &ans, const vector> &baseV) { auto v = createCards(ans, baseV); return calcScore(v[0].first, v[0].second); } lli calcScore(const vector> &ans, const vector> &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> 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> bestAns = ans; while (true) { nowLoopCount++; endTime = std::chrono::system_clock::now(); double elapsed = std::chrono::duration_cast(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; }