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

提出ソース

結果

問題	No.5004 Room Assignment
ユーザー	t33f
提出日時	2021-12-03 01:14:30
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	154 ms / 5,000 ms
コード長	2,585 bytes
コンパイル時間	761 ms
実行使用メモリ	22,392 KB
スコア	138,232,753
平均クエリ数	7643.23
最終ジャッジ日時	2021-12-03 01:14:51
合計ジャッジ時間	20,099 ms
ジャッジサーバーID （参考情報）	judge13 / judge15
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

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

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;

int r = 0, rooms[pmax][4], rmax[pmax], rmin[pmax];

struct Player {
    int id, skill, time;
    Player(int id, int skill, int time) : id(id), skill(skill), time(time) {}
};

vector<Player> players;

const int threshold[] = {3, 3, 4, 4, 5, 6};

int main() {
    { int t, r; cin >> t >> r; assert(t == T); assert(r == R); }
    int p = 0;
    for (int i = 0; i < pmax; i++) for (int j = 0; j < 4; j++) rooms[i][j] = -1;
    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);
        }
        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 = threshold[abs(s - 50) / 10];
            for (int j = 0; j < r; j++) {
                if (rooms[j][3] != -1) continue;
                const int tmp = max(0, s - rmax[j]) + max(0, rmin[j] - s);
                if (penalty > tmp) {
                    penalty = tmp;
                    bestr = j;
                }
            }
            if (bestr != -1) {
                output.emplace_back(rooms[bestr][0], i);
                for (int k = 0; ; k++) {
                    assert(k < 4);
                    if (rooms[bestr][k] == -1) {
                        rooms[bestr][k] = i;
                        rmax[bestr] = max(rmax[bestr], s);
                        rmin[bestr] = min(rmin[bestr], s);
                        break;
                    }
                }
            } else {
                assert(rooms[r][0] == -1);
                rooms[r][0] = i;
                rmax[r] = rmin[r] = s;
                r++;
            }
        }
        write_output(output);
    }

    // for (int i = 0; i < r; i++) {
    //     for (int k = 0; k < 4; k++) {
    //         if (rooms[i][k] != 0) {
    //             Player p = players[rooms[i][k]];
    //             cerr << p.id << ' ' << p.skill << ' ' << p.time << "; ";
    //         }
    //     }
    //     cerr << endl;
    // }
}

yukicoder

結果

テストケース

ソースコード