B- Berland Music Codeforces Educational Round 120
Approach-
The base idea for solving this problem is to separate the liked and disliked elements and sort them separately. Since, all the disliked elements should have less rating than those of all the liked ones, the idea is to make a change in disliked elements first and then in liked elements of the array. All the disliked elements should be numbered increasingly from 1 in a sorted manner to satisfy the given condition of minimum deviation from older values.
To accomplish this task we take disliked and liked elements separately in two vectors of pair and then sort them. Now sort both of them and iterate over the disliked vector first making changes at indexes of the elements in the original array. Then iterate over the liked vector elements.
Below is the detailed code in C++ exactly matching with the explanation above.
Code-
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(ii, n) for (ll ii = 0; ii < n; ii++)
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll testcase=1;
cin >> testcase;
f(i, testcase)
{
ll n;
cin>>n;
ll a[n];
f(i,n)
cin>>a[i];
string s;
cin>>s;
vector<pair<ll,ll>>dis, lik;
for(ll i=0;i<n;i++)
{
if(s[i]=='0')
{
dis.push_back({a[i],i});
}
else if(s[i]=='1')
{
lik.push_back({a[i],i});
}
}
sort(dis.begin(), dis.end());
sort(lik.begin(), lik.end());
ll c=1;
for(ll i=0;i<dis.size();i++)
{
a[dis[i].second]=c;
c++;
}
for(ll i=0;i<lik.size();i++)
{
a[lik[i].second]=c;
c++;
}
for(auto x:a)
cout<<x<<" ";
cout<<endl;
}
}
Other Problems from this Contest-
Disclaimer- Everything is published after the actual contest gets over.