結果

問題 No.5004 Room Assignment
ユーザー SDESTINY_kpr
提出日時 2021-12-02 23:52:36
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,347 bytes
コンパイル時間 1,305 ms
実行使用メモリ 41,248 KB
スコア 0
最終ジャッジ日時 2021-12-02 23:52:51
合計ジャッジ時間 14,067 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 99
権限があれば一括ダウンロードができます

ソースコード

diff # 

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