You are not logged in. Please login at www.codechef.com to post your questions!

×

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[left] <= 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[left];
            S[left]=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;     
}
}

asked 16 Jan '13, 10:09

charchit's gravatar image

2★charchit
126149
accept rate: 0%

edited 16 Jan '13, 10:28


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.

link

answered 16 Jan '13, 14:42

anton_lunyov's gravatar image

6★anton_lunyov ♦
6.7k62119138
accept rate: 12%

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 :)

link

answered 16 Jan '13, 22:44

Illusion03's gravatar image

2★Illusion03
8425
accept rate: 16%

thanx dude!!

(17 Jan '13, 15:26) charchit2★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×3,764
×1,070
×21
×2

question asked: 16 Jan '13, 10:09

question was seen: 1,004 times

last updated: 17 Jan '13, 15:26