#include #include #include #include #include using namespace std; vector get_input() { int n; cin >> n; vector ret(n); for (int i = 0; i < n; i++) cin >> ret[i]; return ret; } void write_output(vector > &output) { cout << output.size() << '\n'; for (auto [i, j] : output) cout << i + 1 << ' ' << j + 1 << '\n'; cout.flush(); } constexpr int T = 3600, R = 4, pmax = 5400; struct Player { int id, skill, tick; Player(int id, int skill, int t) : id(id), skill(skill), tick(t) {} }; vector players; struct Room { int members[4], enter_tick[4], rmax, rmin, mem_count = 0; Room() { fill(members, members+4, -1); } int calc_score() const { int E = 0; for (int k = 0; k < mem_count; k++) { for (int j = 0; j < k; j++) { const int merged_t = max(enter_tick[j], enter_tick[k]); E += abs(players[members[j]].tick - merged_t); E += abs(players[members[k]].tick - merged_t); } } const int coeff = mem_count * (mem_count - 1) / 2, d = rmax - rmin, score = max(0, coeff * (200 - d * d) - E); return score; } int calc_score_after_add(const Player p, int t) const { int E = 0; for (int k = 0; k < mem_count; k++) { for (int j = 0; j < k; j++) { const int merged_t = max(enter_tick[j], enter_tick[k]); E += abs(players[members[j]].tick - merged_t); E += abs(players[members[k]].tick - merged_t); } } for (int k = 0; k < mem_count; k++) { E += abs(players[members[k]].tick - t); } const int coeff = mem_count * (mem_count + 1) / 2, d = max(p.skill, rmax) - min(p.skill, rmin), score = max(0, coeff * (200 - d * d) - E); return score; } void add_member(Player p, int t) { assert(mem_count < 4); members[mem_count] = p.id; enter_tick[mem_count] = t; if (mem_count == 0) rmax = rmin = p.skill; else { rmax = max(rmax, p.skill); rmin = min(rmin, p.skill); } mem_count++; } // int get_score_after_merge(const Room& room) { // } }; vector rooms; vector room_of(pmax, -1); const int threshold[][6] = { {4, 5, 7, 8, 9, 9}, // sparse {4, 4, 5, 6, 8, 8}, // default {4, 4, 5, 6, 7, 7}, // dense {3, 3, 3, 4, 4, 4}, // dense {3, 3, 3, 4, 4, 4}, // dense {3, 3, 3, 4, 5, 5}, // dense {3, 3, 3, 4, 5, 5}, // dense }; const int threshold_list[] = { 0, 100, 250, 500 }; int main() { { int t, r; cin >> t >> r; assert(t == T); assert(r == R); } int p = 0; int pcount[30], pcount_max = 20, pc_idx = 0; fill(pcount, pcount+pcount_max, 1); int pcsum = accumulate(pcount, pcount+pcount_max, 0); for (int tick = 0; tick < T; tick++) { vector input = get_input(); const int p0 = p; for (int s : input) { players.emplace_back(p++, s, tick); } pcsum += input.size() - pcount[pc_idx]; pcount[pc_idx] = input.size(); pc_idx = (pc_idx + 1) % pcount_max; vector > output; for (int p1 = p0; p1 < p; p1++) { const auto [i, s, t] = players[p1]; // find best room for i int bestr = -1, penalty = threshold[pcsum / pcount_max][abs(s - 50) / 10]; for (int j = 0; j < rooms.size(); j++) { const Room &rm = rooms[j]; if (rm.mem_count == 4) continue; const int tmp = max(s, rm.rmax) - min(s, rm.rmin); if (penalty > tmp) { const int score = rm.calc_score(), new_score = rm.calc_score_after_add(players[p1], tick); const int lb = threshold_list[rm.mem_count]; if (score < new_score and new_score > lb) { penalty = tmp; bestr = j; } } } if (bestr != -1) { output.emplace_back(rooms[bestr].members[0], i); rooms[bestr].add_member(players[p1], tick); } else { rooms.emplace_back(); rooms.back().add_member(players[p1], tick); } } write_output(output); } // int total = 0; // for (int i = 0; i < rooms.size(); i++) { // const Room &rm = rooms[i]; // const int score = rooms[i].calc_score(); // total += score; // cerr << i << ' ' << rm.rmax - rm.rmin << ' ' << score << '\t'; // for (int k = 0; k < rm.mem_count; k++) { // const Player &p = players[rm.members[k]]; // cerr << p.id << ' ' << p.skill << ' ' << p.tick << "; "; // } // cerr << endl; // } // cerr << total << endl; }