結果

問題 No.5004 Room Assignment
ユーザー t33ft33f
提出日時 2021-12-03 01:14:30
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.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
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
    // }
}
0