#721730 (C++17) No.5004 Room Assignment

• 問題: No.5004 Room Assignment
• ユーザー: t33f
• 提出日時: 2021-12-04 15:21:27
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 154 ms / 5,000 ms
• コード長: 5,088 bytes
• コンパイル時間: 902 ms
• 実行使用メモリ: 22,380 KB
• スコア: 139,622,909
• 平均クエリ数: 7614.97
• 最終ジャッジ日時: 2021-12-04 15:21:49
• 合計ジャッジ時間: 21,601 ms
• ジャッジサーバーID （参考情報）: judge11 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	138 ms; 21,948 KB
testcase_01	AC	140 ms; 22,032 KB
testcase_02	AC	139 ms; 22,140 KB
testcase_03	AC	139 ms; 21,780 KB
testcase_04	AC	139 ms; 21,912 KB
testcase_05	AC	141 ms; 22,020 KB
testcase_06	AC	139 ms; 21,924 KB
testcase_07	AC	135 ms; 21,912 KB
testcase_08	AC	139 ms; 21,972 KB
testcase_09	AC	139 ms; 21,960 KB
testcase_10	AC	141 ms; 21,936 KB
testcase_11	AC	141 ms; 22,128 KB
testcase_12	AC	140 ms; 21,816 KB
testcase_13	AC	140 ms; 21,960 KB
testcase_14	AC	140 ms; 21,948 KB
testcase_15	AC	142 ms; 22,140 KB
testcase_16	AC	142 ms; 22,128 KB
testcase_17	AC	141 ms; 21,924 KB
testcase_18	AC	142 ms; 21,888 KB
testcase_19	AC	139 ms; 21,948 KB
testcase_20	AC	139 ms; 21,948 KB
testcase_21	AC	139 ms; 21,816 KB
testcase_22	AC	141 ms; 21,948 KB
testcase_23	AC	141 ms; 22,140 KB
testcase_24	AC	138 ms; 22,092 KB
testcase_25	AC	143 ms; 21,900 KB
testcase_26	AC	143 ms; 21,900 KB
testcase_27	AC	140 ms; 22,152 KB
testcase_28	AC	141 ms; 21,936 KB
testcase_29	AC	140 ms; 22,128 KB
testcase_30	AC	142 ms; 22,128 KB
testcase_31	AC	138 ms; 21,984 KB
testcase_32	AC	140 ms; 22,104 KB
testcase_33	AC	141 ms; 22,380 KB
testcase_34	AC	139 ms; 22,380 KB
testcase_35	AC	140 ms; 22,140 KB
testcase_36	AC	141 ms; 22,212 KB
testcase_37	AC	140 ms; 22,140 KB
testcase_38	AC	143 ms; 22,356 KB
testcase_39	AC	144 ms; 21,948 KB
testcase_40	AC	142 ms; 21,912 KB
testcase_41	AC	139 ms; 22,128 KB
testcase_42	AC	142 ms; 21,780 KB
testcase_43	AC	142 ms; 22,140 KB
testcase_44	AC	141 ms; 21,984 KB
testcase_45	AC	140 ms; 22,140 KB
testcase_46	AC	148 ms; 21,780 KB
testcase_47	AC	142 ms; 22,376 KB
testcase_48	AC	142 ms; 21,936 KB
testcase_49	AC	143 ms; 21,960 KB
testcase_50	AC	144 ms; 21,792 KB
testcase_51	AC	141 ms; 21,792 KB
testcase_52	AC	140 ms; 22,344 KB
testcase_53	AC	142 ms; 21,924 KB
testcase_54	AC	139 ms; 21,924 KB
testcase_55	AC	141 ms; 21,960 KB
testcase_56	AC	139 ms; 21,924 KB
testcase_57	AC	139 ms; 21,972 KB
testcase_58	AC	142 ms; 21,912 KB
testcase_59	AC	142 ms; 21,956 KB
testcase_60	AC	141 ms; 21,924 KB
testcase_61	AC	139 ms; 21,924 KB
testcase_62	AC	143 ms; 22,092 KB
testcase_63	AC	140 ms; 21,972 KB
testcase_64	AC	140 ms; 21,972 KB
testcase_65	AC	142 ms; 21,912 KB
testcase_66	AC	144 ms; 21,888 KB
testcase_67	AC	141 ms; 21,924 KB
testcase_68	AC	143 ms; 21,900 KB
testcase_69	AC	145 ms; 22,128 KB
testcase_70	AC	142 ms; 21,900 KB
testcase_71	AC	140 ms; 22,032 KB
testcase_72	AC	154 ms; 21,984 KB
testcase_73	AC	140 ms; 22,140 KB
testcase_74	AC	138 ms; 21,960 KB
testcase_75	AC	137 ms; 21,912 KB
testcase_76	AC	137 ms; 21,948 KB
testcase_77	AC	140 ms; 21,948 KB
testcase_78	AC	150 ms; 21,900 KB
testcase_79	AC	142 ms; 21,912 KB
testcase_80	AC	145 ms; 22,020 KB
testcase_81	AC	143 ms; 21,936 KB
testcase_82	AC	138 ms; 21,936 KB
testcase_83	AC	140 ms; 22,140 KB
testcase_84	AC	140 ms; 21,960 KB
testcase_85	AC	141 ms; 21,816 KB
testcase_86	AC	144 ms; 21,912 KB
testcase_87	AC	141 ms; 22,092 KB
testcase_88	AC	144 ms; 21,768 KB
testcase_89	AC	145 ms; 22,032 KB
testcase_90	AC	140 ms; 21,780 KB
testcase_91	AC	139 ms; 21,924 KB
testcase_92	AC	138 ms; 22,368 KB
testcase_93	AC	143 ms; 21,948 KB
testcase_94	AC	142 ms; 22,128 KB
testcase_95	AC	137 ms; 21,936 KB
testcase_96	AC	141 ms; 21,924 KB
testcase_97	AC	140 ms; 21,780 KB
testcase_98	AC	144 ms; 21,912 KB
testcase_99	AC	144 ms; 21,960 KB

ソースコード

#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[30], pcount_max = 20, 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;
}