結果

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

ソースコード

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

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