Page 2 of 2
solved it
Posted: Sun Feb 10, 2008 3:50 pm
by Sedefcho
OK, seems I had almost done it (solved it) by the
time I have made my previous post. So you may ignore it,
as I have it ACC now with a runtime of about 1/2 second (0.460 secs).
Still, I make one assumption up-front which I don't like
very much, although everyone can check up-front
that this assumption is true (or can also prove it quite
easily in a mathematical way).
The assumption is that each number from 1 to 2,000,000
has at most 20 prime factors and actually only two numbers
have exactly 20 prime factors: 1048576 and 1572864.
Good luck to everyone.
Re: 11353 - A different kind of Sorting
Posted: Tue Aug 24, 2010 5:20 am
by Nursoltan_h
My code runs in 11.094sec
Code: Select all
/*
NAME : Nursoltan
PROB :
LANG : C++
*/
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <utility>
#include <queue>
using namespace std;
#define MAX 2000000
#define INF INT_MAX
#define eps (1e-9)
#define FOR(_i,_k,_n) for(int (_i)=(_k); (_i)<(_n); (_i)++)
#define FORR(_i,_k,_n) for(int (_i)=(_k); (_i)>=(_n); (_i)--)
#define CLR(_x) memset((_x),0,sizeof(_x))
#define SQR(_x) ((_x)*(_x))
#define all(_x) _x.begin(),_x.end()
#define vc vector<int>
#define pb push_back
#define mp make_pair
#define iss istringstream
#define oss ostringstream
#define px first
#define py second
typedef long long ll;
typedef pair <int,int> point;
int ABS(int _x){ return _x>0?_x:-_x; }
bool sieve[MAX+1];
int a[MAX+1],N,n=1;
set<int> st[20];
set<int>::iterator it;
int main()
{
clock_t start = clock();
a[0]=1;
for(int i=2; i<=MAX; i++){
if(!sieve[i]){ a[n++]=i; st[0].insert(i); }
for(int j=2*i; j<=MAX; j+=i) sieve[j]=1;
}
N=n;
for(int i=1; i<20&&N<MAX; i++){
for(int j=1; j<n; j++){
for(it=st[i-1].begin(); it!=st[i-1].end()&&int(*it)*a[j]<=MAX; it++){
if(st[i].count(int(*it)*a[j])) break;
st[i].insert(int(*it)*a[j]);
}
}
for(it=st[i].begin(); it!=st[i].end()&&N<MAX; it++) a[N++]=int(*it);
}
clock_t end = clock();
cout<<N<<" "<<double(end-start)/CLOCKS_PER_SEC;
while(1){
int f;
cin>>f; cout<<a[f-1]<<endl;
}
system("pause");
return 0;
}
How can i optimize my code???
Re: 11353 - A different kind of Sorting
Posted: Fri Aug 27, 2010 8:57 pm
by arifcsecu
try to use sieve method..
in the flying of sieve method , just calculate the factor of all number
then use qsort() / sort()..