# CHEFHACK WA

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;
}
}``````

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

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

1 Like

thanx dude!!

//