結果

問題 No.5004 Room Assignment
ユーザー 👑 Nachia
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0