結果
問題 | No.5004 Room Assignment |
ユーザー |
![]() |
提出日時 | 2021-12-01 04:47:28 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 154 ms / 5,000 ms |
コード長 | 3,221 bytes |
コンパイル時間 | 1,549 ms |
実行使用メモリ | 22,380 KB |
スコア | 137,681,296 |
平均クエリ数 | 7643.20 |
最終ジャッジ日時 | 2021-12-01 04:47:50 |
合計ジャッジ時間 | 20,924 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
ソースコード
#include <cassert>#include <cmath>#include <algorithm>#include <iostream>#include <iomanip>#include <climits>#include <map>#include <queue>#include <set>#include <cstring>#include <vector>using namespace std;typedef long long ll;class UnionFind {public:vector<int> parent;vector<int> _size;UnionFind(int n) {for (int i = 0; i < n; ++i) {parent.push_back(i);_size.push_back(1);}}int find(int x) {if (parent[x] == x) {return x;} else {return parent[x] = find(parent[x]);}}void unite(int x, int y) {x = find(x);y = find(y);if (x == y) return;if (x > y) {parent[x] = y;_size[y] += _size[x];} else {parent[y] = x;_size[x] += _size[y];}}bool same(int x, int y) {return find(x) == find(y);}int size(int x) {return _size[find(x)];}};int T, R;struct Command {int u;int v;Command(int u = -1, int v = -1) {this->u = u;this->v = v;}string to_str() {return to_string(u) + " " + to_string(v);}};class Adv2021 {public:void run() {int N;int id = 1;int counter[101];memset(counter, 0, sizeof(counter));vector<int> started_at(5555, 9999);vector<int> skills[101];UnionFind uf(5555);vector<int> power(5555, 0);for (int t = 0; t < T; ++t) {cin >> N;vector<int> S(N);vector <Command> commands;for (int i = 0; i < N; ++i) {int s;cin >> s;S[i] = s;power[id] = s;skills[s].push_back(id);started_at[id] = t;int u = skills[s].back();int diff = 2;if (abs(s - 50) >= 25) diff = 3;if (abs(s - 50) >= 40) diff = 5;int max_time = -1;int min_time = 9999;int best_v = -1;for (int ns = max(0, s - diff); ns <= min(100, s + diff); ++ns) {if (skills[ns].empty()) continue;for (int v : skills[ns]) {int size = uf.size(u) + uf.size(v);int time = t - started_at[v];if (not uf.same(u, v) && size <= R && max_time < time) {max_time = time;best_v = v;}}}if (best_v != -1) {uf.unite(u, best_v);started_at[uf.find(u)] = min(started_at[u], started_at[best_v]);started_at[uf.find(best_v)] = min(started_at[u], started_at[best_v]);commands.push_back(Command(u, best_v));}counter[s]++;id++;}cout << commands.size() << endl;for (Command &cmd : commands) {cout << cmd.to_str() << endl;}cout << flush;}vector<bool> checked(5555, false);for (int i = 1; i < id; ++i) {int p = uf.find(i);if (checked[p]) continue;if (uf.size(p) == R) continue;checked[p] = true;fprintf(stderr, "x: %d, size: %d, st: %d\n", power[p], uf.size(p), started_at[p]);}for (int x = 0; x <= 100; ++x) {// fprintf(stderr, "x: %d, cnt: %d\n", x, counter[x]);}}};int main() {cin >> T >> R;Adv2021 solver;solver.run();return 0;}