Skip to content

Instantly share code, notes, and snippets.

@maxiwoj
Last active April 30, 2016 12:34
Show Gist options
  • Save maxiwoj/2e403159838c1f26bb2dfd9ef91ac67b to your computer and use it in GitHub Desktop.
Save maxiwoj/2e403159838c1f26bb2dfd9ef91ac67b to your computer and use it in GitHub Desktop.
#include <iostream>
#define N 1000000
using namespace std;
struct node{
int rank;
int num_of_friends;
node *parent;
};
int generateNum[100000000];
//-------------------------
node * makeSet();
//---------------------------
node *findSet(node *x);
//------------------------------
int GetCallerId(int k);
//--------------------------
void unite(node *x,node *y);
int GetCalledId(int k);
int main() {
node **clients=new node *[N];
for(int i=0;i<N;i++){
clients[i]=makeSet();
}
node *MD=clients[524287];
int counter=0;
int num=1;
int caller,called;
while(findSet(MD)->num_of_friends<990000){
caller=GetCallerId(num);
called=GetCalledId(num);
if (caller!=called) {
unite(clients[caller],clients[called]);
counter++;
}
num++;
if(num%1000==0) cout<<findSet(MD)->num_of_friends<<endl;
}
cout<<"num of friends of PM:"<<findSet(MD)->num_of_friends<<endl;
cout<<"num of succesful calls:"<<counter<<endl<<"num of all calls:"<<num;
delete[] clients;
return 0;
}
//-------------------------
node * makeSet(){
node * v = new node;
v->num_of_friends=1;
v->parent=v;
v->rank=0;
return v;
}
//---------------------------
node *findSet(node *x){
if (x->parent == x) {
return x;
}
else {
return x->parent = findSet(x->parent);
}
}
//--------------------------
void unite(node *x,node *y){
node *Rx=findSet(x);
node *Ry=findSet(y);
if(Rx==Ry) return;
else{
if(Rx->rank < Ry->rank){
Rx->parent=Ry;
Ry->num_of_friends+=Rx->num_of_friends;
}
else{
Ry->parent=Rx;
Rx->num_of_friends+=Ry->num_of_friends;
if(Ry->rank==Rx->rank) Rx->rank++;
}
}
return;
}
//------------------------------
int GetCallerId(int k){
unsigned long long int number;
k=(2*k)-1;
if(k<=55){
number= (unsigned long long int) (k * k * k * 300007);
number-=k*200003;
number+=100003;
number%=1000000;
generateNum[k]= (int) number;
return (int) number;
}
else{
number= (unsigned long long int) ((generateNum[k-24] + generateNum[k-55]) % 1000000);
generateNum[k]= (int) number;
return (int) number;
}
}
int GetCalledId(int k){
unsigned long long int number;
k=2*k;
if(k<=55){
number= (unsigned long long int) (k * k * k * 300007);
number-=k*200003;
number+=100003;
number%=1000000;
generateNum[k]= (int) number;
return (int) number;
}
else{
number= (unsigned long long int) ((generateNum[k-24] + generateNum[k-55]) % 1000000);
generateNum[k]= (int) number;
return (int) number;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment