ivnikkk

Untitled

May 10th, 2022
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.70 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS  
  2. #define debug(l) cerr<<#l<<' '<<l<<'\n';
  3. #include "bits/stdc++.h"
  4. using namespace std;
  5. #define all(pref) pref.begin(), pref.end()
  6. typedef long long ll;
  7. typedef pair<ll, ll> pll;
  8. typedef long double ld;
  9. vector<vector<ll>> gr;
  10. vector<vector<ll>> siz;
  11. vector<ll> clr;
  12. ll ans = 0;
  13. void dfs(ll v, ll p) {
  14.     siz[clr[v]][v] = 1;
  15.     for (ll& u : gr[v]) {
  16.         if (u != p) {
  17.             dfs(u, v);
  18.             siz[0][v] += siz[0][u];
  19.             siz[1][v] += siz[1][u];
  20.         }
  21.     }
  22.     if (siz[1][v] == siz[0][v])ans++;
  23. }
  24. signed main() {
  25. #ifdef _DEBUG
  26.     freopen("input.txt", "r", stdin);
  27.     freopen("output.txt", "w", stdout);
  28. #endif
  29.     ios_base::sync_with_stdio(false);
  30.     cin.tie(nullptr);
  31.     cout.tie(nullptr);
  32.     ll t;
  33.     cin >> t;
  34.     while (t--) {
  35.         ll n, k;
  36.         cin >> n >> k;
  37.         vector<ll> a(n);
  38.         map<ll, ll> cnt;
  39.         for (ll i = 0; i < n; i++) {
  40.             cin >> a[i];
  41.             cnt[a[i]]++;
  42.         }
  43.         sort(all(a));
  44.         a.resize(unique(all(a)) - a.begin());
  45.         ll ans = -1;
  46.         pll cur;
  47.         n = a.size();
  48.         for (ll l = 0; l < n; l++) {
  49.             if (cnt[a[l]] >= k) {
  50.                 ll r = l;
  51.                 while (r < n && cnt[a[r]] >= k && a[(r==l?l:r)] - a[(r==l?l:r-1)] <= 1)r++;
  52.                 r--;
  53.                 if (a[r] - a[l] > ans) {
  54.                     ans = a[r] - a[l];
  55.                     cur = { a[l],a[r] };
  56.                 }
  57.                 l = r;
  58.             }
  59.         }
  60.         if (ans == -1) {
  61.             cout << ans << '\n';
  62.         }
  63.         else {
  64.             cout << cur.first << ' ' << cur.second << '\n';
  65.         }
  66.  
  67.     }
  68.  
  69. }
  70.  
Advertisement
Add Comment
Please, Sign In to add comment