Solution of Problem F from BAIUST Junior IUPC (Individual) 2024

f_soln_baiust_jr_iupc_indi_24.cpp

#include <bits/stdc++.h>
 
using namespace std;
 
#define LL long long
#define sz(x) (int)(x).size()
#define trace(x) cerr << #x << " = " << x << '\n';
#define trace2(x,y) cerr << #x << "=" << x << "\t" << #y << "=" << y << '\n';
template<class T> T lcm(T a, T b) {return ( abs(a * b) / gcd(a, b));}
#define MOD			(int)(1e9 + 7)
#define N 10000007
 
bool num[N];
int primes[N];
int total = 0;
int divisors[500];
int ndiv;
 
void sieve()
{
	int i, k;
 
	memset(num, true, sizeof(num));
	num[0] = num[1] = false;	
	for(i = 4; i < N; i+= 2) num[i] = false;
 
	for(i = 3; i < N; i += 2) {
		if(num[i]) {
			k = i;
			while(k+i < N) {
				k += i;
				num[k] = false;
			}
		}
	}
}
 
void store()
{
	for(int i = 2; i < N; i++)
		if(num[i]) primes[total++] = i;
}
 
void solve(int t) {
    int n, k;
    cin >> n >> k;
 
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
 
    sort(arr.begin(), arr.end());
 
    map<int, int> prime_indices;
 
    for (int i = 0; i < n; i++) {
        if(num[arr[i]]) {
            prime_indices[arr[i]] = i;
        }
    }
 
    for(auto p : prime_indices) {
        if(p.second - k < 0) {
            cout << n + (p.second - k) << " ";
        } 
        else {
            cout << (p.second - k) << " ";
        }
    }
    cout << endl;
}
 
int main() {
    sieve();
    store();
 
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int T;
    cin >> T;
    cin.ignore();
 
    for(int t = 0; t < T; t++) {
        solve(t);
    }
}