×

# CHEFHACK WA

 0 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 #include #include #include #include #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 &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= 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 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

 1 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. answered 16 Jan '13, 14:42 6.7k●62●119●138 accept rate: 12%
 0 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 :) answered 16 Jan '13, 22:44 84●2●5 accept rate: 16% thanx dude!! (17 Jan '13, 15:26) charchit2★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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