PROBLEM LINK:
Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1
Author: Daanish Mahajan
Tester : Radoslav Dimitrov
Editorialist: Aman Dwivedi
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
There are N players with IDs from 1 to N, who are participating in the Javelin throw competition which has two rounds. The first is the qualification round, followed by the final round. The qualification round has gotten over, and you are given the longest distance that each of the N players has thrown as A_1, A_2, \ldots, A_N. Now, the selection process for the final round happens in the following two steps:
-
If the longest throw of a player in the qualification round is greater than or equal to the qualification mark of M cm, they qualify for the final round.
-
If after step 1, less than X players have qualified for the finals, the remaining spots are filled by players who have thrown the maximum distance among the players who have not qualified yet.
You are given the best throws of the N players in the qualification round A_1, A_2, \ldots, A_N and the integers M and X. Print the list of the players who will qualify for the finals in increasing order of their IDs.
EXPLANATION:
The problem is straightforward, we need to do as the problem statement says. Simply sort the array in decreasing order of the distance remembering the ID of the players with their distance.
Now after that, start traversing the array there are two conditions when a player can be qualified for the finals:
-
If the player’s throw distance is more than the qualification mark M, he simply qualifies for the final.
-
If the player’s throw distance is less than the qualification mark M but the number of players in the final is less than X, the player qualifies for the final.
We can simply push the IDs of the players that are qualified for the finals. Since we need IDs of the qualified players in increasing order, we can sort the array which contains the qualified players ID and print this list.
TIME COMPLEXITY:
O(N*log(N)) per test case
SOLUTIONS:
Author
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define rb pop_back
#define ti tuple<int, int, int>
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define mp make_pair
#define mt make_tuple
using namespace std;
const int maxt = 1000;
const string newln = "\n", space = " ";
const int minm = 5000, maxm = 8000;
int main()
{
int t, n, m, x, y;
cin >> t;
while(t--){
cin >> n >> m >> x;
vector<pii> v;
for(int i = 0; i < n; i++){
cin >> y;
v.pb({y, i + 1});
}
sort(v.begin(), v.end(), greater<pii>());
int cnt = 0;
vector<int> ans;
for(pii p : v){
if(p.first >= m){
ans.pb(p.second); cnt++;
}else{
if(cnt < x){
ans.pb(p.second); cnt++;
}else{
break;
}
}
}
sort(ans.begin(), ans.end());
int sz = ans.size();
cout << sz << " ";
for(int i = 0; i < sz; i++){
cout << ans[i] << (i == sz - 1 ? newln : space);
}
}
}
Tester
def solve_case():
n, m, k = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
with_ids = [(x, i + 1) for i, x in enumerate(a)]
answer = []
for v, i in sorted(with_ids, reverse=True):
if len(answer) < k or v >= m:
answer.append(i)
print(len(answer), *sorted(answer))
cases = int(input())
for _ in range(cases):
solve_case()
Editorialist
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n,m,x;
cin>>n>>m>>x;
int a[n];
vector <int> ans;
for(int i=0;i<n;i++)
{
cin>>a[i];
if(a[i]>=m)
{
ans.push_back(i+1);
a[i]=-1;
}
}
while(ans.size()<x)
{
int idx = 0;
int fi_idx = 0;
while(idx<n)
{
if(a[idx]>a[fi_idx])
fi_idx = idx;
idx++;
}
ans.push_back(fi_idx+1);
a[fi_idx] = -1;
}
sort(ans.begin(),ans.end());
cout<<ans.size()<<" ";
for(auto itr: ans)
cout<<itr<<" ";
cout<<endl;
}
int main()
{
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
int t;
cin>>t;
while(t--)
solve();
}