#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #pragma GCC optimize("Ofast") #define REP(i, N) for (int i = 0; i < (int)N; i++) #define FOR(i, a, b) for (int i = a; i < (int)b; i++) #define ALL(x) (x).begin(), (x).end() using namespace std; using Pii = pair; constexpr int inf = 1 << 30; template string to_string(T s); template string to_string(pair p); string to_string(char c) { return string(1, c); } string to_string(string s) { return s; } string to_string(const char s[]) { return string(s); } template string to_string(T v) { if (v.empty()) return "{}"; string ret = "{"; for (auto x : v) ret += to_string(x) + ","; ret.back() = '}'; return ret; } template string to_string(pair p) { return "{" + to_string(p.first) + ":" + to_string(p.second) + "}"; } void debug() { cerr << endl; } template void debug(Head head, Tail... tail) { cerr << to_string(head) << " "; debug(tail...); } 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; } constexpr int T = 3600, R = 4; int id = 1; struct Player { int idx; int t; int s; int e; Player() : e(0) {} }; struct Room { vector players; int mn, mx; int t; int e; Room() {} Room(Player player) { players.push_back(player); mn = mx = player.s; e = 0; t = player.t; } int merged_gap(Room &room) { return max(mx, room.mx) - min(mn, room.mn); } void merge(Room &room, int t) { for (auto &player : players) { player.e += (t - player.t) * room.players.size(); } for (auto &player : room.players) { player.e += (t - player.t) * players.size(); chmin(mn, player.s); chmax(mx, player.s); } for (auto &player : room.players) { players.push_back(player); } e = players.size() * (players.size() - 1) / 2 * (200 - (mx - mn) * (mx - mn)); t = inf; for (auto player : players) { e -= player.e; chmin(t, player.t); } e = max(0, e); } }; int main(int argc, char **argv) { int _; cin >> _ >> _; vector rooms; vector thrs(101, 3); vector ns(100, 1.5); REP(i, 101) { int d = min(i, 100 - i); if (d < 10) thrs[i] = 5; else if (d < 20) thrs[i] = 4; else thrs[i] = 3; } int E = 0; REP(t, T) { int N; cin >> N; ns.push_back(N); double ave = 0; REP(i, 50) ave += ns[ns.size() - 1 - i] / 50; vector ans; REP(i, N) { Player player; player.idx = id++; player.t = t; cin >> player.s; rooms.emplace_back(player); } auto merge = [&]() { while (1) { int best = inf; Pii cand(-1, -1); REP(i, rooms.size()) { FOR(j, i + 1, rooms.size()) { if (rooms[i].players.size() + rooms[j].players.size() <= 4) { if (rooms[i].merged_gap(rooms[j]) <= thrs[rooms[i].mn] + (ave < 1.1)) { int v = rooms[i].merged_gap(rooms[j]) - max(rooms[i].mx - rooms[i].mn, rooms[j].mx - rooms[j].mn); if (v < best) { best = v; cand = {i, j}; } } } } } if (best < inf) { ans.emplace_back(rooms[cand.first].players[0].idx, rooms[cand.second].players[0].idx); rooms[cand.first].merge(rooms[cand.second], t); rooms.erase(rooms.begin() + cand.second); if (rooms[cand.first].players.size() == 4) { E += rooms[cand.first].e; if (0 && rooms[cand.first].e < 1000) debug(rooms[cand.first].e, rooms[cand.first].mn, rooms[cand.first].mx); rooms.erase(rooms.begin() + cand.first); } } else { break; } } }; merge(); if (t + 1 == T) { REP(i, 101) thrs[i] = 10; merge(); } for (int j = rooms.size() - 1; j >= 0; --j) { if (rooms[j].t < t - 150) { E += rooms[j].e; rooms.erase(rooms.begin() + j); } } cout << ans.size() << endl; for (auto p : ans) cout << p.first << " " << p.second << endl; } for (auto &room : rooms) E += room.e; debug(E); return 0; }