namespace atcoder {} #ifdef LOCAL #define dbg(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl; #else #define NDEBUG #define dbg(x) true; #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #endif #ifdef GTEST #include #endif #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #ifdef PERF #include #endif using namespace std; using namespace atcoder; #define fast_io \ ios_base::sync_with_stdio(false); \ cin.tie(0); \ cout.tie(0); #define ll long long int #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define reps(i, n) for (int i = 1; i <= (int)(n); i++) #define REP(i, n) for (int i = n - 1; i >= 0; i--) #define REPS(i, n) for (int i = n; i > 0; i--) #define MOD (long long int)(1e9 + 7) #define INF (int)(1e9) #define LINF (long long int)(1e18) #define chmax(a, b) a = (((a) < (b)) ? (b) : (a)) #define chmin(a, b) a = (((a) > (b)) ? (b) : (a)) #define ALL(v) v.begin(), v.end() typedef pair Pii; typedef pair Pll; constexpr double PI = acos(-1); #ifdef NDEBUG #define CHECK(v1, op, v2) #else #define CHECK(v1, op, v2) \ if (!((v1)op(v2))) { \ cerr << "ERROR:" << (v1) << " " << (v2) << endl; \ assert((v1)op(v2)); \ } #endif long double nCr(const int n, const int r) { long double ret = 1; rep(t, r) { ret *= (n - t); ret /= (r - t); } return ret; } template string to_string(const vector& vec) { string ret = ""; rep(i, vec.size()) { ret += vec[i].to_string(); if (i + 1 != vec.size()) { ret += ","; } } return ret; } template ostream& operator<<(ostream& os, const vector& vec) { os << to_string(vec); return os; } uint32_t xorshift() { static uint32_t x = 12345789; static uint32_t y = 362436069; static uint32_t z = 521288629; static uint32_t w = 88675123; uint32_t t; t = x ^ (x << 11); x = y; y = z; z = w; w ^= t ^ (t >> 8) ^ (w >> 19); return w; } int rand(const uint32_t l, const uint32_t r) { return xorshift() % (r - l) + l; } uint32_t rand_other_than(const uint32_t l, const uint32_t r, const uint32_t other) { const uint32_t num = rand(l, r - 1); return num + (num >= other); } template const T& rand_vec(const vector& vec) { assert(vec.size() > 0); return vec[rand(0, vec.size())]; } template void shuffle(vector& vec) { rep(l, (int)vec.size() - 1) { const int idx = rand(l, vec.size()); swap(vec[idx], vec[l]); } } class Timer { chrono::system_clock::time_point _start, _end; ll _sum = 0, _count = 0; public: void start() { _start = chrono::system_clock::now(); } void stop() { _end = chrono::system_clock::now(); } void add() { const chrono::system_clock::time_point now = chrono::system_clock::now(); _sum += static_cast( chrono::duration_cast(now - _start).count()); _count++; } ll sum() const { return _sum / 1000; } int count() const { return _count; } string average() const { if (_count == 0) { return "NaN"; } return to_string(_sum / 1000 / _count); } void reset() { _start = chrono::system_clock::now(); _sum = 0; _count = 0; } inline int ms() const { const chrono::system_clock::time_point now = chrono::system_clock::now(); return static_cast( chrono::duration_cast(now - _start).count() / 1000); } inline int ns() const { const chrono::system_clock::time_point now = chrono::system_clock::now(); return static_cast( chrono::duration_cast(now - _start).count()); } }; #ifdef LOCAL struct Timers : unordered_map { friend ostream& operator<<(ostream& os, const Timers& timers) { for (const auto& pa : timers) { os << pa.first << " time: " << pa.second.sum() / 1000 << " count: " << pa.second.count() << endl; } return os; } }; #else struct Timers { struct Dummy { void start() const {} void add() const {} }; Dummy dummy; const Dummy& operator[](const std::string& str) { return dummy; } friend ostream& operator<<(ostream& os, const Timers& timers) { return os; } }; #endif Timers global_timers; /* start */ Timer global_timer; int N; struct Card{ ll a,b; static Card Mean(const Card& X, const Card& Y){ const ll a = (X.a+Y.a)/2; const ll b = (X.b+Y.b)/2; return {a,b}; } ll Cost() const{ return max(abs(a), abs(b)); } int OmoteUra()const{ return (a > 0 ? 2 : 0) + (b > 0 ? 1 : 0); } }; vector inputCards; constexpr ll base = 5 * (ll)(1e17); const int Q = 50; vector> globalAns; void Do(vector>& ans, vector& cards, const int i, const int j){ assert((int)ans.size() < Q); assert(i!=j); const auto card = Card::Mean(cards[i], cards[j]); cards[i] = card; cards[j] = card; ans.push_back({i,j}); } void PrintAns(const vector>& vec){ cout << vec.size()<>N; inputCards.resize(N); rep(i,N){ ll a,b; cin>>a>>b; a -= base; b -= base; inputCards[i].a = a; inputCards[i].b = b; } } friend ostream& operator<<(ostream& os, const Output& output) { return os; } }; /* start */ vector PARAMS = {1.0, 0.1}; /* start */ class Solver { public: Solver() {} void Solve() { // (表,裏)x(+,-)の組数を等しくしたい vector> ansCommands; rep(_t, 6){ // (表が+? 2 :0) + (裏が+? 1: 0) vector counts(4); int minEval = INF; pair bestCommand = {-1,-1}; rep(i, N){ const auto& card = inputCards[i]; const int val = card.OmoteUra(); counts[val]++; } const auto func = [](const vector& counts){ int minCount = INF; int maxCount = 0; rep(i, 4){ chmin(minCount, counts[i]); chmax(maxCount, counts[i]); } return maxCount - minCount; }; minEval = func(counts); rep(i, N){ rep(j, N){ auto newCounts = counts; const auto& card0 = inputCards[i]; const auto& card1 = inputCards[j]; const auto newCard = Card::Mean(card0, card1); newCounts[card0.OmoteUra()]--; newCounts[card1.OmoteUra()]--; newCounts[newCard.OmoteUra()] += 2; const auto eval = func(newCounts); if(eval < minEval){ bestCommand = {i, j}; } } } if(bestCommand.first == -1) continue; ansCommands.push_back(bestCommand); const auto newCard = Card::Mean(inputCards[bestCommand.first], inputCards[bestCommand.second]); inputCards[bestCommand.first] = newCard; inputCards[bestCommand.second] = newCard; } ll totalMinCost = LINF; size_t bestSize = 0; ll totalBestScore = 0; // 1/2, 1/4, 1/8, ... // 乱択貪欲 long double sumA = 0; long double sumB = 0; vector remainIds(N); vector ansIds; std::iota(ALL(remainIds), 0); long double weight = 1.0; while(remainIds.size()){ if((int)remainIds.size() != 1){ weight *= 0.5; } ll minCost = LINF; ll bestSumA = 0; ll bestSumB = 0; int best_i = -1; rep(i, remainIds.size()){ const auto id = remainIds[i]; if(id == 0 && (int)remainIds.size() >= 2) continue; const auto& card = inputCards[id]; const auto nextSumA = sumA + card.a * weight; const auto nextSumB = sumB + card.b * weight; const ll cost = max(abs(nextSumA), abs(nextSumB)); if(cost < minCost){ minCost = cost; bestSumA = nextSumA; bestSumB = nextSumB; best_i = i; } } assert(best_i >= 0); ansIds.push_back(remainIds[best_i]); swap(remainIds[best_i], remainIds.back()); remainIds.pop_back(); sumA = bestSumA; sumB = bestSumB; cerr << sumA<<" "<= 2) { int idx = 0; for (int i = 1; i < argc; ++i) { PARAMS[idx++] = std::stod(argv[i]); } } Timer timer; timer.start(); Output::StaticInit(cin); Solver solver; solver.Solve(); return 0; }