UVA 11353 - A Different Kind of Sorting

UVA Sep 1, 2020

Problem PDF

Solution:

/******************************************************************
***   Problem       :                                           ***
***   Author        : Shipu Ahamed (Psycho Timekiller)          ***
***   E-mail        : [email protected]                   ***
***   University    : BUBT,Dept. of CSE                         ***
***   Team          : BUBT_Psycho                               ***
***   My Blog       : http://shipuahamed.blogspot.com           ***
***   Facebook      : http://www.facebook.com/DeesheharaShipu   ***
******************************************************************/

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define pi 2*acos(0.0)
#define all(v) v.begin(),v.end()

//input
#define si(t) scanf("%d",&t)
#define sl(t) scanf("%lld",&t)
#define sf(t) scanf("%f",&t)
#define sd(t) scanf("%lf",&t)
#define sc(c) scanf("%c",&c)
#define sii(a,b) scanf("%d%d",&a,&b)
#define sll(a,b) scanf("%lld%lld",&a,&b)

//Output
#define P(a) printf("%d\n",a)
#define PL(a) printf("%lld\n",a)
#define PF(a) printf("%f\n",a)
#define PDB(a) printf("%lf\n",a)
#define PN(a) printf("%d ",a)
#define PLN(a) printf("%lld ",a)
#define PFN(a) printf("%f ",a)
#define PDBN(a) printf("%lf ",a)
#define PP(a,b) printf("%d %d\n",a,b)
#define PPN(a,b) printf("%d %d ",a,b)
#define PPL(a,b) printf("%lld %lld\n",a,b)
#define PPLN(a,b) printf("%lld %lld ",a,b)

#define CP(a) cout< pii;
typedef  pair piii;
typedef  pair pll;
typedef  pair psi;
typedef  vector vi;
typedef  vector vll;
typedef  vector vpii;
typedef  vector vs;
typedef  set si;
typedef  set ss;
typedef  map mii;
typedef  map mll;
typedef  map msi;

template string toString( T Number ){stringstream st;st << Number;return st.str();}
template  T SOD(T n) {__typeof(n) sum=0;for(__typeof(n) i=1;i*i<=n;i++)sum+=(n%i)?0:((i*i==n)?i:i+n/i);return sum;}


//For Define
#define forab(i,a,b) for(__typeof(b) i=(a);i<=(b);i++)
#define for0(i,n) forab(i,0,(n)-1)
#define for1(i,n) forab(i,1,n)
#define rforba(i,b,a) for(__typeof(b) i=(b);i>=(a);i--)
#define rfor0(i,n) rforba(i,(n)-1,0)
#define rfor1(i,n) rforba(i,n,1)
#define forstl(i,s) for(__typeof((s).end()) i=(s).begin(); i != (s).end(); i++)

//Debug
#define dbg(x) cout << #x << " -> " << (x) << endl;
#define dbgsarr(i,a) cout<<#a<<"["< "< "< "<>p ; return p;}

ll pow(ll a,ll b, ll m) { ll res = 1; while(b) { if(b & 1) { res = ( (res % m) * (a % m) ) %m ; } a= ((a%m) * (a%m)) %m; b >>= 1; } return res; }
ll modInverse(ll a, ll m){return pow(a,m-2,m);}

////============ CONSTANT ===============////
#define mx7   10000007
#define mx6   2000006
#define mx5   100005
#define inf   1<<30                                           //infinity value
#define eps   1e-9
#define mx    (1500)
#define mod   1000000007
////=====================================////

struct factcount
{
    ll value=0,cnt=0;

}A[mx6];

bool prime[mx6+10];
ll pd[mx6+10];
int k=1;

void seive()
{
    for(int i=4;i<=mx6;i+=2)
        prime[i]=1;

    prime[0]=1;
    prime[1]=1;
    pd[0]=2;

    for(ll i=3;i<=mx6-6;i+=2)
    {
        if(!prime[i])
        {
            pd[k++]=i;
            ll mul = i<<1;
            ll j=i;
            for(j*=i;j<=mx6;j+=mul)
            {
                prime[j]=1;
            }
        }
    }
//    PN(k),PL(pd[k-1]);
}

void fact(int n)
{
    int p=n;
    A[p].value=n;

    int sq = sqrt(n),i=0;
    int c=0;
    while(n!=1)
    {
        if(pd[i]>sq || i==k-1) break;

        while(n%pd[i]==0)
        {
            n/=pd[i];
            c++;
        }
        i++;
    }
    if(n!=1)
    {
        c++;
    }

    A[p].cnt=c;
}

bool cmp(factcount a, factcount b)
{
    if(a.cnt==0 || b.cnt==0) return false;
    if(a.cnt==b.cnt)
        return a.value
https://github.com/Shipu/OnlineJudgeProblemSolutionWithCPlusPlus/tree/master/uva/11353/11353.cpp

Tags

Great! You've successfully subscribed.
Great! Next, complete checkout for full access.
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.