Skip to content

Instantly share code, notes, and snippets.

@iambrj
Created December 11, 2022 14:15
Show Gist options
  • Save iambrj/1fe3a92cdb799d60e45aa9403d269522 to your computer and use it in GitHub Desktop.
Save iambrj/1fe3a92cdb799d60e45aa9403d269522 to your computer and use it in GitHub Desktop.
#include <bits/stdc++.h>
using namespace std;
map<int, int> m;
void merge(int array[], int const left, int const mid,
int const right)
{
auto const subArrayOne = mid - left + 1;
auto const subArrayTwo = right - mid;
auto *leftArray = new int[subArrayOne],
*rightArray = new int[subArrayTwo];
for (auto i = 0; i < subArrayOne; i++)
leftArray[i] = array[left + i];
for (auto j = 0; j < subArrayTwo; j++)
rightArray[j] = array[mid + 1 + j];
auto indexOfSubArrayOne
= 0,
indexOfSubArrayTwo
= 0;
int indexOfMergedArray
= left;
bool leftInserted = false;
while (indexOfSubArrayOne < subArrayOne
&& indexOfSubArrayTwo < subArrayTwo) {
if (leftArray[indexOfSubArrayOne]
<= rightArray[indexOfSubArrayTwo]) {
leftInserted = true;
array[indexOfMergedArray]
= leftArray[indexOfSubArrayOne];
indexOfSubArrayOne++;
leftInserted = true;
} else {
array[indexOfMergedArray]
= rightArray[indexOfSubArrayTwo];
m[rightArray[indexOfSubArrayTwo]] += !leftInserted;
indexOfSubArrayTwo++;
}
indexOfMergedArray++;
}
while (indexOfSubArrayOne < subArrayOne) {
array[indexOfMergedArray]
= leftArray[indexOfSubArrayOne];
indexOfSubArrayOne++;
indexOfMergedArray++;
}
while (indexOfSubArrayTwo < subArrayTwo) {
array[indexOfMergedArray]
= rightArray[indexOfSubArrayTwo];
indexOfSubArrayTwo++;
indexOfMergedArray++;
}
delete[] leftArray;
delete[] rightArray;
}
void countingMergeSort(int array[], int const begin, int const end)
{
if (begin >= end)
return;
auto mid = begin + (end - begin) / 2;
countingMergeSort(array, begin, mid);
countingMergeSort(array, mid + 1, end);
merge(array, begin, mid, end);
}
int solve(vector<int> a) {
int n = a.size();
auto *array = new int[n];
for(int i = 0; i < n; i++) {
array[i] = a[i];
}
countingMergeSort(array, 0, n - 1);
int ans = 0;
for(auto [k, v] : m) {
ans = max(ans, v);
}
return ans;
}
int main() {
std::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
//cout << setprecision(8);
//int t; cin >> t; while(t--)
int n; cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i++) cin >> a[i];
cout << solve(a);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment