結果
| 問題 | No.5004 Room Assignment |
| ユーザー |
 SDESTINY_kpr
|
| 提出日時 | 2021-12-02 23:52:36 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 3,347 bytes |
| コンパイル時間 | 1,305 ms |
| 実行使用メモリ | 41,248 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2021-12-02 23:52:51 |
| 合計ジャッジ時間 | 14,067 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
| testcase_65 | -- | - |
| testcase_66 | -- | - |
| testcase_67 | -- | - |
| testcase_68 | -- | - |
| testcase_69 | -- | - |
| testcase_70 | -- | - |
| testcase_71 | -- | - |
| testcase_72 | -- | - |
| testcase_73 | -- | - |
| testcase_74 | -- | - |
| testcase_75 | -- | - |
| testcase_76 | -- | - |
| testcase_77 | -- | - |
| testcase_78 | -- | - |
| testcase_79 | -- | - |
| testcase_80 | -- | - |
| testcase_81 | -- | - |
| testcase_82 | -- | - |
| testcase_83 | -- | - |
| testcase_84 | -- | - |
| testcase_85 | -- | - |
| testcase_86 | -- | - |
| testcase_87 | -- | - |
| testcase_88 | -- | - |
| testcase_89 | -- | - |
| testcase_90 | -- | - |
| testcase_91 | -- | - |
| testcase_92 | -- | - |
| testcase_93 | -- | - |
| testcase_94 | -- | - |
| testcase_95 | -- | - |
| testcase_96 | -- | - |
| testcase_97 | -- | - |
| testcase_98 | -- | - |
| testcase_99 | -- | - |
ソースコード
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <cstdlib>
#include <functional>
#include <climits>
#include <time.h>
#include <chrono>
#include <random>
using namespace std;
using P = pair<int, int>;
using ll = long long;
#define rep(i,n) for (int i=0;i<(n);i++)
const int INF = 1 << 30;
struct UnionFind {
vector<int> par; // par[i]:iの親の番号 (例) par[3] = 2 : 3の親が2
vector<int> siz; // size[i]:iの属する木の要素数
UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
for (int i = 0; i < N; i++) par[i] = i;
siz = vector<int>(N);
for (int i = 0;i < N;i++) siz[i] = 1;
}
int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
if (par[x] == x) return x;
return par[x] = root(par[x]);
}
void unite(int x, int y) { // xとyの木を併合
int rx = root(x); //xの根をrx
int ry = root(y); //yの根をry
if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
siz[ry] += siz[rx];
}
int size(int x) { // データxが属する木の要素数を得る : size(x) = {xの木の要素数}
int rx = root(x);
return siz[rx];
}
bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
int rx = root(x);
int ry = root(y);
return rx == ry;
}
};
vector<int> topo_sort(int n,vector<vector<int>> G,vector<int> d) {
vector<int> res;
queue<int> q;
rep(i, n) if (d[i] == 0) q.push(i);
while (!q.empty()) {
int now = q.front(); q.pop();
res.push_back(now);
for (auto e : G[now]) {
d[e]--;
if (d[e] == 0) q.push(e);
}
}
return res;
}
ll powmod(ll a, ll b, ll mod = LLONG_MAX) {
if (b == 1) return a;
ll res;
if (b % 2 == 0) res = powmod((a * a) % mod, b / 2, mod);
else res = powmod((a * a) % mod, b / 2, mod) * a;
return res;
}
int t, r;
int cnt = 0;
UnionFind UF(5400);
vector<int> s(5400);
void solve() {
int n;
cin >> n;
rep(i, n) cin >> s[cnt + i];
cnt += n;
int M = 0;
vector<P> ans(0);
rep(i, cnt-1) {
P res = P(INF,-1);
for (int j=i+1;j<cnt;j++){
if (s[i] == s[j] && UF.size(i) + UF.size(j) <= 4) {
UF.unite(i, j);
M++;
ans.push_back(P(i, j));
res = P(INF,-1);
break;
}
else {
if (res.first > abs(s[i] - s[j]) && UF.size(i) + UF.size(j) <= 4) {
res = P(abs(s[i] - s[j]), j);
}
}
}
if (res.second != (-1)) {
UF.unite(i, res.second);
M++;
ans.push_back(P(i, res.second));
}
}
cout << M << endl;
rep(i,M) {
cout << ans[i].first << " " << ans[i].second << endl;
}
}
int main()
{
cin >> t >> r;
rep(i, t) solve();
return 0;
}