fork download 
  1. /*
  2. Task: 1433D
  3. Date: Dec 19, 2020
  4. Author: aLittleLove (Minh Vu)
  5. */
  6.  
  7. #include<bits/stdc++.h>
  8. #define rep(i,n) for (int i=0, _n=n; i<_n; i++)
  9. #define FOR(i,a,b) for (int _a=(a), _b=(b), i=_a; _a<=_b?i<=_b:i>=_b; _a<=_b?i++:i--)
  10. #define _mem(a, b) memset(a, (b), sizeof(a))
  11. #define pb push_back
  12. #define fi first
  13. #define se second
  14. #define sz(a) int((a).size())
  15.  
  16. using namespace std;
  17. typedef long long ll;
  18. typedef int64_t i64;
  19. typedef pair<int, int> pii;
  20. typedef vector<pii> vii;
  21. typedef vector<int> vi;
  22. const int N = 5e3 + 5;
  23. const int inf = 1e9;
  24. const int mod = 1e9 + 7;
  25. const double pi = atan(1) * 4.0;
  26. template<typename T, typename U> inline void mini(T &x, U y) { if(y < x) x = y; }
  27. template<typename T, typename U> inline void maxi(T &x, U y) { if(x < y) x = y; }
  28.  
  29. i64 _pow(i64 x, i64 y)
  30. {
  31.     if (y==0) return 1;
  32.     i64 tmp = _pow(x, y>>1ll);
  33.     if (y&1) return (tmp%mod * tmp%mod * x%mod)%mod;
  34.     return (tmp%mod * tmp%mod)%mod;
  35. }
  36.  
  37. int a[N];
  38. vector<int> adj[N];
  39. vector<pii> e;
  40. bool vis[N];
  41.  
  42. void dfs(int u)
  43. {
  44.     vis[u] = 1;
  45.     for (int v: adj[u])
  46.     {
  47.         if (vis[v]) continue;
  48.         e.pb({u, v});
  49.         dfs(v);
  50.     }
  51. }
  52.  
  53. void Solve()
  54. {
  55.     int n; cin >> n;
  56.     for (int i=1; i<=n; i++) cin >> a[i], adj[i].clear();
  57.     e.clear();
  58.     memset(vis,0,sizeof vis);
  59.     for (int i=1; i<=n; i++)
  60.     {
  61.         for (int j=i+1; j<=n; j++)
  62.         {
  63.             if (a[i]==a[j]) continue;
  64.             adj[i].pb(j);
  65.             adj[j].pb(i);
  66.         }
  67.     }
  68.     for (int i=1; i<=n; i++) if (!vis[i]) dfs(i);
  69.     if (e.size()!=n-1)
  70.     {
  71.         cout << "NO\n";
  72.         return;
  73.     }
  74.     cout << "YES\n";
  75.     for (pii x: e) cout << x.fi << " " << x.se << '\n';
  76. }
  77.  
  78. int main()
  79. {
  80.     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  81.     //freopen("input.txt","r",stdin);
  82.     int nTest; cin >> nTest;
  83.     while (nTest--) Solve();
  84.  
  85.     return 0;
  86. }
Success #stdin #stdout 0s 4928KB
comments (?)
stdin 
4
5
1 2 2 1 3
3
1 1 1
4
1 1000 101 1000
4
1 2 3 4
stdout 
YES
1 2
2 4
4 3
3 5
NO
YES
1 2
2 3
3 4
YES
1 2
2 3
3 4
https://ideone.com/vUndfX
Codeforces 1433D
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!