11353 - A Different Kind of Sorting

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

solved it

Post by Sedefcho » Sun Feb 10, 2008 3:50 pm

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.

Nursoltan_h
New poster
Posts: 9
Joined: Sat Jun 12, 2010 2:11 pm
Location: Ulaanbaatar, Mongolia
Contact:

Re: 11353 - A different kind of Sorting

Post by Nursoltan_h » Tue Aug 24, 2010 5:20 am

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???

arifcsecu
Learning poster
Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong
Contact:

Re: 11353 - A different kind of Sorting

Post by arifcsecu » Fri Aug 27, 2010 8:57 pm

try to use sieve method..
in the flying of sieve method , just calculate the factor of all number
then use qsort() / sort()..
Try to catch fish rather than asking for some fishes.

Post Reply

Return to “Volume 113 (11300-11399)”