#pragma GCC optimize ("O3") #pragma GCC optimize ("unroll-loops") #pragma GCC target ("avx2") #include #include #include #include #include #include #include #include #include #include #include #include #include #include struct xorshift64 { unsigned long long int x = 88172645463325252ULL; inline unsigned short nextUShort() { x = x ^ (x << 7); return x = x ^ (x >> 9); } inline unsigned int nextUShortMod(unsigned long long int mod) { x = x ^ (x << 7); x = x ^ (x >> 9); return ((x & 0x0000ffffffffffff) * mod) >> 48; } inline unsigned int nextUInt() { x = x ^ (x << 7); return x = x ^ (x >> 9); } inline unsigned int nextUIntMod(unsigned long long int mod) { x = x ^ (x << 7); x = x ^ (x >> 9); return ((x & 0x00000000ffffffff) * mod) >> 32; } inline unsigned long long int nextULL() { x = x ^ (x << 7); return x = x ^ (x >> 9); } inline double nextDouble() { x = x ^ (x << 7); x = x ^ (x >> 9); return (double)x * 5.42101086242752217e-20; } }; struct timer { double t = 0.0; double lastStop = 0.0; bool stopped = false; timer() { restart(); } inline void restart() { t = now(); stopped = false; } inline void start() { if (stopped) { t += now() - lastStop; stopped = false; } } inline void stop() { if (!stopped) { lastStop = now(); stopped = true; } } inline double time() { if (stopped) return lastStop - t; else return now() - t; } inline double now() { unsigned long long l, h; __asm__ ("rdtsc" : "=a"(l), "=d"(h)); #ifdef LOCAL return (double)(l | h << 32) * 2.857142857142857e-10; // 1 / 3.5e9, for local (Ryzen 9 3950X) #else //return (double)(l | h << 32) * 3.5714285714285715e-10; // 1 / 2.8e9, for AWS EC2 C3 (Xeon E5-2680 v2) //return (double)(l | h << 32) * 3.4482758620689656e-10; // 1 / 2.9e9, for AWS EC2 C4 (Xeon E5-2666 v3) return (double)(l | h << 32) * 3.333333333333333e-10; // 1 / 3.0e9, for AWS EC2 C5 (Xeon Platinum 8124M / Xeon Platinum 8275CL) #endif } }; using namespace std; typedef long long int ll; typedef pair Pii; const ll mod = 1000000007; timer theTimer; xorshift64 theRandom; mt19937 theMersenne(1); // constants constexpr int turn_limit = 3600; constexpr int r = 4; constexpr int n_total = 5400; constexpr array score_mult = {0, 0, 1, 3, 6}; constexpr int base_score = 200; // structs struct room_info { int room_host; int min_skill; int max_skill; vector turn_joined; room_info(int host_id, int host_skill, int create_turn) { this->room_host = host_id; this->min_skill = host_skill; this->max_skill = host_skill; this->turn_joined = vector({create_turn}); } void join(int member_skill, int join_turn) { assert((int) this->turn_joined.size() < 4); assert(this->turn_joined[this->turn_joined.size()-1] <= join_turn); this->min_skill = min(this->min_skill, member_skill); this->max_skill = max(this->max_skill, member_skill); this->turn_joined.push_back(join_turn); } int calc_raw_score() { int score = (base_score - (max_skill - min_skill) * (max_skill - min_skill)) * score_mult[this->turn_joined.size()]; for (int i = 0; i < (int) this->turn_joined.size() - 1; i++) { for (int j = i + 1; j < (int) this->turn_joined.size(); j++) { score -= this->turn_joined[j] - this->turn_joined[i]; } } return score; } int calc_score() { int score = calc_raw_score(); return max(0, score); } int simulate_score(int member_skill, int join_turn) { assert((int) this->turn_joined.size() < 4); assert(this->turn_joined[this->turn_joined.size()-1] <= join_turn); int temp_min_skill = min(this->min_skill, member_skill); int temp_max_skill = max(this->max_skill, member_skill); int score = (base_score - (temp_max_skill - temp_min_skill) * (temp_max_skill - temp_min_skill)) * score_mult[this->turn_joined.size() + 1]; for (int i = 0; i < (int) this->turn_joined.size() - 1; i++) { for (int j = i + 1; j < (int) this->turn_joined.size(); j++) { score -= this->turn_joined[j] - this->turn_joined[i]; } } for (int i = 0; i < (int) this->turn_joined.size(); i++) { score -= join_turn - this->turn_joined[i]; } return score; } }; // internals int turn_count = 0; vector > room_list(5); vector get_input() { int n; cin >> n; vector added_player(n); for (auto &x: added_player) cin >> x; return added_player; } void output(vector op) { cout << op.size() << endl; for (auto &x: op) cout << x.first << " " << x.second << endl; } void solve() { auto calc_total_score = [&]() { int total_score = 0; for (int i = 2; i <= 4; i++) { for (auto &room: room_list[i]) total_score += room.calc_score(); } return total_score; }; int current_player_id = 1; while (turn_count < turn_limit) { auto input = get_input(); vector op; for (auto &skill: input) { int best_room_score_delta = -1; int best_room_idx_i = -1; int best_room_idx_j = -1; for (int i = 1; i <= 3; i++) { for (int j = 0; j < (int) room_list[i].size(); j++) { if (max(room_list[i][j].max_skill, skill) - min(room_list[i][j].min_skill, skill) <= 3) { int room_score_delta = room_list[i][j].simulate_score(skill, turn_count) - room_list[i][j].calc_score(); if (room_score_delta > best_room_score_delta) { best_room_score_delta = room_score_delta; best_room_idx_i = i; best_room_idx_j = j; } } } } if (best_room_idx_i != -1 && best_room_idx_j != -1) { op.emplace_back(room_list[best_room_idx_i][best_room_idx_j].room_host, current_player_id); room_list[best_room_idx_i][best_room_idx_j].join(skill, turn_count); room_list[best_room_idx_i+1].push_back(room_list[best_room_idx_i][best_room_idx_j]); swap(room_list[best_room_idx_i][best_room_idx_j], room_list[best_room_idx_i][room_list[best_room_idx_i].size()-1]); room_list[best_room_idx_i].pop_back(); } else { room_list[1].push_back(room_info(current_player_id, skill, turn_count)); } current_player_id++; } #ifdef DEBUG cerr << "turn_count = " << setw(4) << turn_count << ", score = " << setw(7) << calc_total_score() << endl; #endif output(op); turn_count++; } cerr << "score = " << calc_total_score() << endl; } int main(int argc, char *argv[]) { cin.tie(0); ios::sync_with_stdio(false); int _t, _r; cin >> _t >> _r; solve(); return 0; }