Skip to content

Instantly share code, notes, and snippets.

@krisys
Last active June 13, 2019 06:48
Show Gist options
  • Save krisys/4670777 to your computer and use it in GitHub Desktop.
Save krisys/4670777 to your computer and use it in GitHub Desktop.
FindTheMin
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a) FOR(i, 0, a)
#define all(a) a.begin(), a.end()
#define SORT(a) sort(all(a))
#define in(a,b) ( (b).find(a) != (b).end())
#define pb push_back
#define VI vector<int>
using namespace std;
inline bool is_looping(VI &nos, int k, int n){
if(n - 1 - 2 *k < 0)
return false;
if(nos[n-k] != nos[n - 2 * k - 1])
return false;
for(int i = n-1; i >= n-k; i--){
if(nos[i] != nos[i-k -1])
return false;
}
return true;
}
int main(){
int T;
cin >> T;
REP(tc, T){
cout << "Case #" << tc + 1 << ": ";
long long n, k, a, b, c, r;
cin >> n >> k;
cin >> a >> b >> c >> r;
VI nos(10000000), counters(2*k, 0);
nos[0] = a;
if(nos[0] < 2 * k)
counters[nos[0]]++;
FOR(i, 1, k){
nos[i] = (b * nos[i-1] + c) % r;
// We keep track of all elements which are less than 2*k.
// since we will not be inserting any element more than 2*k
if(nos[i] < 2 * k)
counters[nos[i]]++;
}
/* Set works like a heap */
set<int> available;
FOR(i, 0, 2*k){
if(!counters[i])
available.insert(i);
}
int index = k, cycle_start = -1;
FOR(i, k, n){
// pick the smallest element from the heap.
set<int>::iterator it = available.begin();
nos[index++] = *it;
counters[*it]++;
// remove the newly inserted element from heap.
available.erase(it);
if(nos[i-k] < 2 * k)
counters[nos[i-k]]--;
if(nos[i-k] < 2 * k && counters[nos[i-k]] == 0){
/* if the element at index (i-k) is not used anywhere else
in the range (i - k, i) then we insert it again in the heap. */
available.insert(nos[i-k]);
}
// Check if there is a loop in the numbers generated.
if(is_looping(nos, k, index)){
cycle_start = index - k;
break;
}
}
if(cycle_start == -1){
cout << nos[n-1] << endl;
}
else{
cout << nos[ cycle_start + ((n - cycle_start) % (k + 1) - 1)] << endl;
}
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment