tests/performance/15_shuffle0.sy


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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

int hashmod;

const int maxn = 10000000;
const int maxm = 10000000;
int bucket[maxn];
int head[maxn];
int next[maxm];
int nextvalue[maxm];
int key[maxm];
int value[maxm];
int cnt;

int keys[maxm];
int values[maxm];
int requests[maxm];
int ans[maxm];

int hash(int k){
    return k % hashmod;
}

int insert(int k, int v){
    int h = hash(k);
    if (head[h] == 0){
        cnt = cnt + 1;
        head[h] = cnt;
        key[cnt] = k;
        value[cnt] = v;
        next[cnt] = 0;
        nextvalue[cnt] = 0;
        return 0;
    }
    int p = head[h];
    while (p != 0){
        if (key[p] == k){
            cnt = cnt + 1;
            nextvalue[cnt] = nextvalue[p];
            nextvalue[p] = cnt;
            value[cnt] = v;
            return 1;
        }
        p = next[p];
    }
    cnt = cnt + 1;
    next[cnt] = head[h];
    head[h] = cnt;
    key[cnt] = k;
    value[cnt] = v;
    nextvalue[cnt] = 0;
    return 0;
}

int reduce(int k){
    int h = hash(k);
    int p = head[h];

    while (p != 0){
        if (key[p] == k){
            int ret = 0;
            int x = p;
            while (x != 0){
                ret = ret + value[x];
                x = nextvalue[x];
            }
            return ret;
        }
        p = next[p];
    }
    return 0;
}

int main(){
    hashmod = getint();
    int ks = getarray(keys);
    int vs = getarray(values);
    int ms = getarray(requests);

    starttime();

    int i = 0;
    while (i < ks){
        insert(keys[i], values[i]);
        i = i + 1;
    }
    i = 0;
    while (i < ms){
        ans[i] = reduce(requests[i]);
        i = i + 1;
    }
    stoptime();
    putarray(ms, ans);
    return 0;
}