QualificationRound No.3 Find the Min

3_FindTheMin.cpp

#include <iostream>
#include <cstdio>
#include <vector>
#include <list>
using namespace std;

long getNext(long a, long b, long c, long r){
    return (b * a + c) % r;
}

vector<long> getKnownList(long n, long k, long a,
        long b, long c, long r){
    vector<long> knownList;
    knownList.push_back(a);
    for(int i = 1; i < k; ++i){
        a = getNext(a, b, c, r);
        knownList.push_back(a);
    }
    return knownList;
}

vector<long> getLoopList(vector<long> known, long k){
    long start = 0;
    list<long> stack;
    for(int i = 0; i <= k; ++i){
        if(i != 0){
            if(find(stack.begin(), stack.end(), known[i-1])!=stack.end()
                    &&
                find(known.begin()+i, known.begin()+k+i, known[i-1]) == known.end()){
                stack.remove(known[i-1]);
                known.push_back(known[i-1]);
                continue;
            }
        }
        while(find(known.begin()+i, known.begin()+k+i, start) != known.end()){
            stack.push_back(start);
            start += 1;
        }
        known.push_back(start);
        start += 1;
    }
    return vector<long>(known.begin() + k, known.end());
}

long evaluate(long n, long k, long a, long b, long c, long r){
    vector<long> knownList = getKnownList(n, k, a, b, c, r);
    vector<long> loopList = getLoopList(knownList, k);
    long mod;
    long answer;
    if((n-k) < (k+1)){
        mod = (n - k) % (k + 1);
    }else{
        mod = (n - (k + k+1)) % (k + 1);
    }
    if(mod == 0){
        answer = loopList.back();
    }else{
        answer = loopList[mod-1];
    }
    knownList.clear();
    loopList.clear();
    vector<long>().swap(knownList);
    vector<long>().swap(loopList);
    return answer;
}

int main(){
    int T;
    long k, n, a, b, c, r;
    scanf("%d", &T);
    for(int i=0; i<T; ++i){
        scanf("%ld %ld", &n, &k);
        scanf("%ld %ld %ld %ld", &a, &b, &c, &r);
        printf("Case #%d: %ld\n", i+1,
                evaluate(n,k,a,b,c,r));
    }
}