結果

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

ソースコード

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

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