trafik

Untitled

Aug 10th, 2021
734
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.02 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using ll = long long;
  4. using namespace std;
  5.  
  6. int main() {
  7.     ios::sync_with_stdio(0);
  8.     cin.tie(0);
  9.  
  10.     ll n, k; cin >> n >> k;
  11.     vector<ll> a(n + 1); for (int i = 1; i <= n; ++i) cin >> a[i];
  12.     ll i = 1, j = 2, ibest = 0, jbest = 1e6;
  13.     vector<ll> t(k + 1, 0);
  14.     ++t[a[i]];
  15.     ++t[a[j]];
  16.     while (j <= n) {
  17.         bool isEmpty = false;
  18.         for (int x = 1; x <= k; ++x) {
  19.             if (t[x] == 0) {
  20.                 if (j == n) {
  21.                     ++j;
  22.                     break;
  23.                 }
  24.                 isEmpty = true;
  25.                 ++j;
  26.                 ++t[a[j]];
  27.                 break;
  28.             }
  29.         }
  30.         if (isEmpty) continue;
  31.         if (t[a[i]] == 1 && j - i < jbest - ibest) {
  32.             jbest = j;
  33.             ibest = i;
  34.             if (j == n) break;
  35.             ++j;
  36.             ++t[a[j]];
  37.         }
  38.         else {
  39.             --t[a[i]];
  40.             ++i;
  41.         }
  42.     }
  43.     cout << ibest << " " << jbest;
  44. }
Advertisement
Add Comment
Please, Sign In to add comment