Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- void CountSort(std::vector<std::pair<int, int>> &a, int place) {
- std::vector<std::pair<int, int>> tmp(a.size());
- std::vector<int> cnt(10);
- for (auto &[val, ind] : a) {
- ++cnt[(val / place) % 10];
- }
- for (int i = 1; i < 10; ++i) {
- cnt[i] += cnt[i - 1];
- }
- for (auto &it : a) {
- tmp[--cnt[(it.first / place) % 10]] = it;
- }
- a.swap(tmp);
- }
- int FindMaxElement(std::vector<std::pair<int, int>> &a) {
- int answ = a.front().first;
- for (auto &[val, ind] : a) {
- answ = std::max(answ, val);
- }
- return answ;
- }
- void RadixSort(std::vector<std::pair<int, int>> &a) {
- int maxx = FindMaxElement(a);
- for (int p = 1; maxx / p > 0; p *= 10) CountSort(a, p);
- }
- signed main() {
- int n;
- std::cin >> n;
- std::vector<std::pair<int, int>> a(n);
- for (int i = 0; i < n; ++i) {
- std::cin >> a[i].first;
- a[i].second = i;
- }
- RadixSort(a);
- int answ = n + 1;
- for (int i = 0; i < n - 1; ++i) {
- if (a[i].first == a[i + 1].first) {
- answ = std::min({answ, a[i].second, a[i + 1].second});
- }
- }
- if (answ == n + 1) {
- std::cout << "We don't have it\n";
- } else {
- std::cout << answ + 1 << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment