Posts

Showing posts with the label graph

Floyd cycle detection algorithm for linera time and linear space

inline int FloydCycleFind ( int x0 ){ x0 %= m ; if ( ! k ) return x0 ; int hare = f ( f ( x0 )), tortoise = f ( x0 ); while ( tortoise != hare ){ hare = f ( f ( hare )); tortoise = f ( tortoise ); } int mu = 0 ; hare = x0 ; while ( tortoise != hare ){ hare = f ( hare ); tortoise = f ( tortoise ); mu ++ ; if ( mu == k ) return hare ; } k -= mu ; int lambda = 1 ; hare = f ( tortoise ); while ( hare != tortoise ) hare = f ( hare ), lambda ++ ; k %= lambda ; while ( k ) tortoise = f ( tortoise ), k -- ; return tortoise ; } https://toph.co/p/not-my-fault

UVA 10004

#include<bits/stdc++.h> #define rep0(i,n) for(i=0;i<n;i++) #define rep(i,n) for(i=1;i<=n;i++) #define reps(i,a,n) for(i=a;i<=n;i++) #define mem(ara,n) memset(ara,n,sizeof(ara)) #define memb(ara) memset(ara,false,sizeof(ara)) #define all(x) (x).begin(),(x).end() #define fast ios_base:: sync_with_stdio( false ); cin.tie(0); cout.tie(0); #define eb              emplace_back #define em              emplace #define pb              push_back #define Mp              make_pair #define ff              first #define ss              second #define mod 1000000007 typedef long long ll; using namespace std; const int M = (int)(2e6 + 239); void decitobinbitodeci() {     string binary = bitset<8>(128).to_string(); //to binary     cou...