124C - Prime Permutation - CodeForces Solution

#include <bits/stdc++.h>
#include <assert.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename Q> using priority_queue_r = priority_queue<Q, vector<Q>, greater<Q>>;
using ll = long long;using ld = long double;
#define el '\n'
#define F  first
#define S  second
#define sz(v) (ll)(v).size()
#define ZOON ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FILE freopen("inputf.in", "r", stdin); freopen("outputf.out", "w", stdout);
int dx[]={1, -1, 0, 0, 1, 1, -1, -1}, dy[]={0, 0, 1, -1, 1, -1, -1, 1};
const ll MOD =  998244353, N = 1e3+7, LOG = 20, SQ = 500, MAX_BIT = 59059;const ld EPS = 1e-7;

void sieve(int n, set<int>&s)
{
	vector<int>p;
	vector<int>prime(n+2, 1);
	prime[0] = prime[1] = false;
	for (int i = 2; i <= n; ++i)
	{
		if(!prime[i])continue;

		p.push_back(i);
		for (int j = i*2; j <= n; j+=i)
			prime[j] = 0;
	}


	for(auto i: p)
	{
		if(i*2 <= n)
			s.insert(i);
	}

	if(s.empty())return;

	for (int i = 2, mx = *s.rbegin(); i <= mx ; ++i)
	{
		if(!prime[i])continue;

		for (int j = i*2; j <= n; j+=i)
			s.insert(j);
	}
}



void SOLVE(int test)
{
	string s;cin>>s;
	set<int>inds;

	if(sz(s) < 4)
	{
		cout << "YES\n" << s;
		return;
	}

	sieve(sz(s), inds);


	bool ok = 0;
	char x = 'a';
	vector<int>frq(26, 0);
	for(auto &i: s)
	{
		frq[i-'a']++;

		if(frq[i-'a'] >= sz(inds))ok = 1, x = i;
	}

	if(!ok)
	{
		cout << "NO" << el;
		return;
	}
	for(auto &i: s)i = '*';

	for(auto i: inds)
		s[i-1] = x, frq[x-'a']--;


	for(auto &i: s)
	{
		if(i != '*')continue;
		
		for (int j = 0; j < 26; ++j)
		{
			if(!frq[j])continue;

			frq[j]--, i = (char)(j+'a');
			break;	
		}
	}

	cout << "YES\n";
	cout << s << el;
}



int main()
{
    ZOON

    int test_cases = 1;
    // cin>>test_cases;
    for(int i = 1;i<=test_cases;i++)
    {
        SOLVE(i);
        // cout << el;
    }
 
    return 0;
}