[코드포스 Round 677] D. Districts Connection

 

이것도 보면 모두 같은 숫자만 아니면 어떻게든 정답이 만들어진다. 

그래서 먼저 전부 같은 경우 제외해주고..

 

이제 전부 연결되게 만들어주는게 문제인데.. 오.. 이거 잘 보니 유파로 풀 수 있겠다 싶었다. 집합 하나를 만드는게 목표니깐 집합이 다르고 숫자가 다른 경우에 묶어주는거지. 

 

다음으로 문제가 생겼는데 숫자 범위가 10^9이다. ㅋㅋㅋㅋ 유파 만들면 범위 터져버린다. 근데 보면 n은 5000밖에 안 된다. 그래서 좌표압축 하면 어떨까 싶었음. 그래서 좌표압축하고 유파써서 풀었다. 죄표압축 기억 안 나서 코드 복붙했는데 양심이 조금 찔리는군

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
 
#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
 
using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;
 
vector<int> parent;
 
void    init(int n)
{
	parent.resize(n + 1);
 
	for (int i = 0; i <= n; i++)
		parent[i] = i;
}
 
int     find(int x)
{
	if (x == parent[x])
		return x;
	return (parent[x] = find(parent[x]));
}
 
void    merge(int x, int y)
{
	x = find(x);
	y = find(y);
 
	parent[x] = y;
}
 
class Mapping
{
public:
	void init(const vector<int>& raw, int base = 0)
	{
		start = base;
		arr = raw;
		sort(arr.begin(), arr.end());
		arr.erase(unique(arr.begin(), arr.end()), arr.end());
	}
 
	int get_idx(int k)
	{
		return start + (lower_bound(arr.begin(), arr.end(), k) - arr.begin());
	}
 
	int get_value(int idx)
	{
		return arr[idx - start];
	}
 
	int size()
	{
		return arr.size();
	}
 
private:
	int start;
	vector<int> arr;
};
 
void	solve()
{
	int n;
	scanf("%d", &n);
 
	vector<int> v(n);
	for (int i = 0; i < n; i++)
		scanf("%d", &v[i]);
	
	bool issame = true;
	for (int i = 1; i < n; i++)
	{
		if (v[i] != v[i - 1])
		{
			issame = false;
			break;
		}
	}
	if (issame)
	{
		printf("NO\n");
		return;
	}
 
	Mapping xmap;
	xmap.init(v);
 
	for (int i = 0; i < n; i++)
	{
		v[i] = xmap.get_idx(v[i]);
	}
 
	init(n);
	printf("YES\n");
	for (int i = 0; i < n; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			if (v[i] != v[j] && find(i) != find(j))
			{
				printf("%d %d\n", i + 1, j + 1);
				merge(i, j);
			}
		}
	}
 
}
 
int     main()
{
	int t;
	scanf("%d", &t);
 
	for (int i = 0; i < t; i++)
	{
		solve();
	}
}