CHEFHACK WA

general
, , ,
1

I’ve used sieve of atkin instead of eratosthenes,

extracted all primes into a vector ‘primes’, added cost of all the primes to the ans.

I’ve used a 2D character array, type[][]’ to apply grid hacking if type[i][j]==‘p’ it is skipped (cost of primes is already added in the ans) else they are cracked by ‘crack()’ function.

all the cracked nodes are marked ‘p’ and hence will be skipped later.

#include<iostream>
#include<vector>
#include<math.h>
#include<bitset>
#include<fstream>
#define  limit  10000050
using namespace std;
//bitset<10000050> sieve;
bool sieve[10000050];
char type[355][355];

int N;

void atkin(){
    int root = 3163;
    for (int z = 0; z < limit; z++) sieve[z] = false;
   
    sieve[2]=1;
    sieve[3]=1;
   for (int x = 1; x <= root; x++)
   {
        for (int y = 1; y <= root; y++)
        {
             int n = (4*x*x)+(y*y);
             if (n <= limit && (n % 12 == 1 || n % 12 == 5)) sieve[n] ^= true;
             n = (3*x*x)+(y*y);
             if (n <= limit && n % 12 == 7) sieve[n] ^= true;
             n = (3*x*x)-(y*y);
             if (x > y && n <= limit && n % 12 == 11) sieve[n] ^= true;
        }
   }
   for (int r = 5; r <= root; r++) if (sieve[r]) for (int i = r*r; i < limit; i += r*r) sieve[i] = false;
}

void crack(int i, int j){
    char x= type[i][j];
    type[i][j]='p';
    if (x!='p'){
        if (x == type[i+1][j]) crack(i+1,j);
        if (x == type[i-1][j]) crack(i-1,j);
        if (x == type[i][j+1]) crack(i,j+1);
        if (x == type[i][j-1]) crack(i,j-1);
    }
}

void Qsort(vector<int> &S, int x, int l){
    if (l-x >0){
        int right,left, p;
        right=l;left=x+1; p=x;
        while (S <= S[p] && left<l) left++;
        while (S[right]>= S[p] && right>x) right--;
        
        if (left>=right){
            int temp=S[p];
            S[p]=S[right];
            S[right]=temp;
            if (right>x) Qsort(S, x,right-1);
            if (right<l) Qsort(S, right+1, l);
        }else{
            int temp=S;
            S=S[right];
            S[right]=temp;
            Qsort(S, x,l);
        }
    } 
}
 
main(){
    int T;
    atkin();
    scanf("%d",&T);
    while(T--){
        int pwd;
        scanf("%d",&N);
        for (int i=0; i<N+2; i++){
            type[0][i]='x';
            type[i][0]='x';
            type[i][N+1]='x';
            type[N+1][i]='x';
        }
        
        int matrix[N+2][N+2];
        vector<int> primes;
        for (int i=1; i<=N; i++){
        for (int j=1; j<=N; j++){
            scanf("%d",&pwd);
            
            if (sieve[pwd]==1){ //its prime!!
                primes.push_back(pwd);
                type[i][j]='p';
                matrix[i][j]=pwd;
            }else{
                if (pwd%2==0){
                    type[i][j]='e';
                    matrix[i][j]= pwd/2;
                }else{
                    matrix[i][j]= (pwd+3)/2;
                    type[i][j]='o';
                }
            }
            
        }}// input ends here    
            
        Qsort(primes, 0, primes.size()-1);
        long ans=0;
        int count=0, it=0;
        
        for (int i=0; it<primes.size(); i++){
            while (i==primes[it]){
                ans+=count;
                it++;
            }
            if (sieve[i]==1) count++;
        }
        

        
        for (int i=1; i<=N;i++){
            for (int j=1; j<=N; j++){
                if (type[i][j]!='p'){
                    ans+=matrix[i][j];
                    crack(i,j);
                }
            }
        }
        
        cout<<ans<<endl;     
}
}
2

In GNU C++ compiler used at cocechef int and long are the same types.
You should use long long instead as a type for variable ans.
Refer to the editorial. There is a bold tip there in QUICK EXPLANATION section.

Also you should precalculate index of each prime rather than use loop over all range from 1 to 1e7 for each test. Because of this you will have TLE after fixing the long long bug.

1 Like
3

Hi,

Just a suggestion , c++ already have a sort() stl function , its complexity is equal to nlogn and n^2 in worst case scenario similar to Quick Sort.

It can be used like this -:

sort(primes.begin(),primes.end());

So you could have saved yourself from writing a Quick Sort code again :slight_smile:

1 Like
4

thanx dude!!