結果
問題 | No.5004 Room Assignment |
ユーザー |
![]() |
提出日時 | 2021-12-04 15:31:55 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 161 ms / 5,000 ms |
コード長 | 5,089 bytes |
コンパイル時間 | 901 ms |
実行使用メモリ | 22,380 KB |
スコア | 139,677,869 |
平均クエリ数 | 7614.91 |
最終ジャッジ日時 | 2021-12-04 15:32:16 |
合計ジャッジ時間 | 21,368 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
ソースコード
#include <cstdlib>#include <numeric>#include <cmath>#include <vector>#include <cassert>#include <iostream>using namespace std;vector<int> get_input() {int n; cin >> n;vector<int> ret(n);for (int i = 0; i < n; i++) cin >> ret[i];return ret;}void write_output(vector<pair<int, int> > &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<Player> 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<Room> rooms;vector<int> room_of(pmax, -1);int threshold_list[] = { 0, 110, 147, 211 };double b0 = 4.67, b1 = -0.45, b2 = 0.04;int main(int argc, char **argv) {if (argc > 6) {for (int i = 1; i < 4; i++)threshold_list[i] = atoi(argv[i]);b0 = atof(argv[4]);b1 = atof(argv[5]);b2 = atof(argv[6]);}{ int t, r; cin >> t >> r; assert(t == T); assert(r == R); }int p = 0;int pcount[100], pcount_max = 60, 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<int> 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<pair<int, int> > output;for (int p1 = p0; p1 < p; p1++) {const auto [i, s, t] = players[p1];// find best room for iint bestr = -1,penalty = round(b0 + b1 * pcsum / pcount_max + b2 * abs(s - 50));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 > 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;}