Guest User

Untitled

a guest
Jun 15th, 2024
343
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.18 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. void CountSort(std::vector<std::pair<int, int>> &a, int place) {
  4.     std::vector<std::pair<int, int>> tmp(a.size());
  5.     std::vector<int> cnt(10);
  6.     for (auto &[val, ind] : a) {
  7.         ++cnt[(val / place) % 10];
  8.     }
  9.     for (int i = 1; i < 10; ++i) {
  10.         cnt[i] += cnt[i - 1];
  11.     }
  12.     for (auto &it : a) {
  13.         tmp[--cnt[(it.first / place) % 10]] = it;
  14.     }
  15.     a.swap(tmp);
  16. }
  17.  
  18. int FindMaxElement(std::vector<std::pair<int, int>> &a) {
  19.     int answ = a.front().first;
  20.     for (auto &[val, ind] : a) {
  21.         answ = std::max(answ, val);
  22.     }
  23.     return answ;
  24. }
  25.  
  26. void RadixSort(std::vector<std::pair<int, int>> &a) {
  27.     int maxx = FindMaxElement(a);
  28.     for (int p = 1; maxx / p > 0; p *= 10) CountSort(a, p);
  29. }
  30.  
  31. signed main() {
  32.     int n;
  33.     std::cin >> n;
  34.     std::vector<std::pair<int, int>> a(n);
  35.     for (int i = 0; i < n; ++i) {
  36.         std::cin >> a[i].first;
  37.         a[i].second = i;
  38.     }
  39.     RadixSort(a);
  40.     int answ = n + 1;
  41.     for (int i = 0; i < n - 1; ++i) {
  42.         if (a[i].first == a[i + 1].first) {
  43.             answ = std::min({answ, a[i].second, a[i + 1].second});
  44.         }
  45.     }
  46.     if (answ == n + 1) {
  47.         std::cout << "We don't have it\n";
  48.     } else {
  49.         std::cout << answ + 1 << "\n";
  50.     }
  51.     return 0;
  52. }
Advertisement
Add Comment
Please, Sign In to add comment