結果
問題 | No.5004 Room Assignment |
ユーザー |
👑 ![]() |
提出日時 | 2021-12-01 23:44:02 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 148 ms / 5,000 ms |
コード長 | 4,645 bytes |
コンパイル時間 | 1,049 ms |
実行使用メモリ | 22,364 KB |
スコア | 139,935,047 |
平均クエリ数 | 7643.83 |
最終ジャッジ日時 | 2021-12-01 23:44:26 |
合計ジャッジ時間 | 22,068 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <deque>#include <cmath>using namespace std;using i32 = int32_t;using u32 = uint32_t;using i64 = int64_t;using u64 = uint64_t;#define rep(i,n) for(int i=0; i<(n); i++)vector<int> player_skills;vector<int> player_times;double enter_count_sum;struct Room{int id;vector<int> players;int value_e;Room(int player_id){id = player_id;players = { id };value_e = 0;}int get_num_players() const { return players.size(); }pair<int,int> merge_in(Room another, int tick){value_e += another.value_e;for(int l : players) for(int r : another.players){value_e += tick - player_times[l];value_e += tick - player_times[r];}for(int r : another.players) players.push_back(r);return { id, another.id };}double receive_score(int player_id, int tick){double skill = player_skills[player_id];int min_skill = 100;int max_skill = 0;int min_tick = 1001001;for(auto a : players){min_skill = min(min_skill, player_skills[a]);max_skill = max(max_skill, player_skills[a]);min_tick = min(min_tick, player_times[a]);}if(min_skill <= skill && skill <= max_skill) return 1.0e100;double mid_skill = (min_skill + max_skill) / 2.0;tick -= min_tick;// double w = 4.0;// double w = pow((mid_skill - 50.0) / 50.0, 2.0) * 2.0 + 3.2;// double w = (exp(abs(mid_skill - 50.0) / 50.0 * 0.1) - 1.0) * 2.0 + 3.0;// double w = (exp(pow(abs(mid_skill-50.0), 2.0) / 4500.0) - 1.0) * 2.0 + 3.75;double w = (exp(pow(abs(mid_skill-50.0), 2.0) / 4500.0) - 1.0) * 3.0 + 3.70;double margin_ticks = 30.0;double margin_w = 0.0;// if(tick >= margin_ticks) margin_w += (log(tick / margin_ticks)) * 1.0;// if(tick >= margin_ticks) margin_w += (log(tick / margin_ticks)) * 1.0;margin_w += 1.5 / (enter_count_sum + 0.1) - 1.0;if(tick >= margin_ticks) margin_w += (log(tick / margin_ticks)) * 1.0;margin_w *= 0.5;// if(tick >= margin_ticks) margin_w += (tick - margin_ticks) / 20;if(false){cerr << w;cerr << ", " << enter_count_sum;cerr << "\n";}w += margin_w;double l = min<double>(min_skill, max_skill - w);double r = max<double>(max_skill, min_skill + w);auto skill_dist = abs(mid_skill - skill) / 100.0;// return (l <= skill && skill <= r) ? (100.0 - skill_dist) : 0.0;return (l <= skill && skill <= r) ? (100.0 - skill_dist / w) : 0.0;}};int main(){const double enter_count_delay = 0.95;enter_count_sum = 10;vector<Room> rooms;int num_tick; cin >> num_tick;int max_room_size; cin >> max_room_size;int next_player_id = 1;player_skills.push_back(0);player_times.push_back(0);rep(tick_idx, num_tick){int num_enter; cin >> num_enter;vector<pair<int,int>> buf;enter_count_sum *= enter_count_delay;enter_count_sum += (1.0 - enter_count_delay) * num_enter;rep(enter_idx, num_enter){int enter_id = next_player_id++;int player_skill; cin >> player_skill;player_skills.push_back(player_skill);player_times.push_back(tick_idx);int to_enter = -1;double receive_score_max = 0.0;rep(room_arr_idx, rooms.size()){auto receive_score = rooms[room_arr_idx].receive_score(enter_id, tick_idx);if(receive_score > receive_score_max){to_enter = room_arr_idx;receive_score_max = receive_score;}}if(to_enter == -1){rooms.emplace_back(enter_id);}else{buf.push_back(rooms[to_enter].merge_in(Room(enter_id), tick_idx));if(rooms[to_enter].players.size() >= max_room_size){swap(rooms[to_enter], rooms.back());rooms.pop_back();}}}cout << buf.size() << "\n";for(auto a : buf){cout << a.first << " " << a.second << "\n";}cout << flush;}return 0;}struct ios_do_not_sync {ios_do_not_sync() {ios::sync_with_stdio(false);cin.tie(nullptr);}} ios_do_not_sync_instance;