External link:

https://www.facebook.com/hackercup/scoreboard?round=185564241586420
http://www.facebook.com/notes/facebook-hacker-cup/qualification-round-solutions/598486173500621

Problem C. Find the Min

Note:

.. 注意循环节长度是 k+1。。

const int N = 100009;

int A[N], o[N]; priority_queue<int, vector<int>, greater<int> > Q;
int n, k, a, b, c;

bool cmp(int a, int b){
    return A[a] < A[b];
}

int gao(){

    RST(A); if (a <= k) A[a] = 1;
    a %= MOD, b %= MOD, c %= MOD;

    FOR(i, 1, k){
        a = sum(pdt(b, a), c);
        if (a <= k) A[a] = i + 1;
    }

    n %= ++k; REP(i, k) o[i] = i;
    sort(o, o+k, cmp); CLR(Q); int p = 0;
    A[o[k] = N-1] = INF;

    REP(i, k){
        while (A[o[p]] == i) Q.push(o[p++]);
        if (i == n) return Q.top();
        Q.pop();
    }
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    Rush{
        RD(n, k, a, b, c, MOD);
        OT(gao());
    }
}

Posted by xiaodao
Category: Facebook Hacker Cup