Here is my approach:-
Please comment about its time complexity.
#include <bits/stdc++.h>
using namespace std;
#define IOS
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int32_t main()
{
IOS;
int t;
cin >> t;
while (t–)
{
int n;
cin >> n;
multimap<int, int, greater> mp;
for (int i = 0; i < n; i++)
{
int e;
cin >> e;
mp.insert({e, i});
}
map<int, multimap<int, int>> mpp;
auto i = mp.begin();
for (int a1 = 1; a1 < n + 1; a1++)
{
int a, b;
a = i->first;
b = i->second;
mpp.insert(make_pair(b, multimap<int, int>()));
mpp[b].insert(make_pair(a, a1));
i++;
}
auto itr = mpp.begin();
auto ptr = mp.begin();
for (itr; itr != mpp.end(); itr++)
{
for (ptr = itr->second.begin(); ptr != itr->second.end(); ptr++)
{
cout<<ptr->second<<" ";
}
}
cout << endl;
}
return 0;
}
Binary search? Sort in descending order, then keep searching for the closest-to-left illness level, and keep marking.
Here’s my solution using Binary Search
I am getting TLE error, idk why…?? Any suggestions??
#include<bits/stdc++.h>
using namespace std;
#define long long int;
int forMax(int arr[], int n){
int max = 0;
for(int i=0; i<n; ++i){
if(max < arr[i]){
max = arr[i];
}
}
return max;
}
int forIndex(int arr[], int n, int value){
for(int i=0; i<n; ++i){
if(arr[i] == value){
return i;
}
}
}
int main()
{
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int arr[n];
int output[n];
for(int i=0; i<n; ++i){
cin>>arr[i];
}
for(int i=0; i<n; ++i){
int max = forMax(arr, n);
int index = forIndex(arr, n, max);
arr[index] = -1;
output[index] = i+1;
}
for(auto i:output){
cout<<i<<" ";
}
cout<<endl;
}
return 0;
}
yes please tell .I did the same
I have used map and set to obtain the solution in effective manner. Below i have shared my approach.
#include <bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
int T,N;
cin>>T;
while(T--){
cin>>N;
map<int,set<int>>ill_level;
int num=0;
for(int i=0;i<N;i++){
cin>>num;
ill_level[num].insert(i);
}
int ans[N];
int t=1;
for(auto itr2=ill_level.rbegin();itr2!=ill_level.rend();itr2++){
set<int>s=itr2->second;
for(auto itr=s.begin();itr!=s.end();itr++){
ans[*itr]=t;
t++;
}
}
for(int i=0;i<N;i++)
std::cout << ans[i] <<" ";
cout<<endl;
}
return 0;
}
You might want to use Stable sort