某岛

… : "…アッカリ～ン . .. . " .. .

January 30, 2013

Facebook Hacker Cup 2013 Qualification Round

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。。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

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