QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#153600	#2587. 荣誉称号	eikki	0	2440ms	101476kb	C++20	1.9kb	2023-08-30 12:45:14	2023-08-30 12:45:15

Judging History

你现在查看的是最新测评结果

[2023-08-30 12:45:15]
评测

测评结果：0
用时：2440ms
内存：101476kb

查看

[2023-08-30 12:45:14]
提交

answer

#include <iostream>
#include <vector>
#include <climits>
typedef long long ll;

int a[10000005], b[10000005];
ll c[(1 << 12) + 5][205];
ll cost[(1 << 12) + 5][205];
ll f[(1 << 12) + 5][205];

unsigned int SA, SB, SC; int p, A, B, n, k, m;

unsigned int rng61(){
    SA ^= SA << 16;
    SA ^= SA >> 5;
    SA ^= SA << 1;
    unsigned int t = SA;
    SA = SB;
    SB = SC;
    SC ^= t ^ SA;
    return SC;
}

void gen(){
    std::cin >> n >> k >> m >> p >> SA >> SB >> SC >> A >> B;
    for(int i = 1; i <= p; i++) {
        std::cin >> a[i] >> b[i];
    }
    for(int i = p + 1; i <= n; i++){
        a[i] = rng61() % A + 1;
        b[i] = rng61() % B + 1;
    }
    for (int i = 1; i <= n; i++) {
        int j = i;
        while (j > (1 << k + 1)) j >>= k + 1;
        c[j][a[i] % m] += b[i];
    }
    for (int i = 1; i < (1 << k + 1); i++) {
        for (int q = 0; q < m; q++) {
            for (int e = 0; e < m; e++) {
                cost[i][q] += 1ll * c[i][e] * ((q - e + m) % m);
            }
        }
    }
}

void dp(int node) {
    if (node >= (1 << k)) {
        for (int i = 0; i < m; i++) {
            f[node][(m - i) % m] = cost[node][i];
        }
        return;
    }
    dp(2*node);
    dp(2*node+1);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            ll nvalue = cost[node][j] + f[2*node][(i + j) % m] + f[2*node+1][(i + j) % m];
            f[node][i] = std::min(f[node][i], nvalue);
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int T;
    std::cin >> T;
    while (T--) {
        for (int j = 0; j < (1 << 12) + 5; j++) {
            for (int k1 = 0; k1 < 205; k1++) {
                c[j][k1] = 0;
                cost[j][k1] = 0;
                f[j][k1] = LLONG_MAX/3;
            }
        }
        gen();
        dp(1);
        std::cout << f[1][0] << std::endl;
    }
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0

Wrong Answer

time: 7ms

memory: 25796kb

input:

10
100 6 2 100 233935 922673 177972 100 100
50 10
22 68
21 75
14 95
33 60
55 83
1 92
82 65
83 88
99 58
49 82
70 42
2 59
37 20
18 85
98 76
11 67
52 28
73 66
28 24
49 98
50 1
86 78
43 38
22 94
3 35
35 96
74 37
74 64
84 5
34 38
19 58
9 11
52 77
28 48
66 47
29 12
8 49
83 50
20 31
79 43
6 53
6 68
99 11
8...

output:

result:

wrong answer 6th lines differ - expected: '15283205', found: '15265091'

Test #2:

score: 0

Wrong Answer

time: 1752ms

memory: 26388kb

input:

10
100000 8 50 100000 247575 819409 776601 100 100
89 32
56 35
20 7
49 32
42 55
32 35
24 93
93 90
54 27
5 38
14 56
29 68
10 88
76 99
93 25
21 89
100 79
48 63
81 38
52 35
96 59
12 79
100 55
16 61
90 78
31 16
27 33
22 81
79 67
74 22
60 14
51 63
60 16
27 17
90 85
94 33
16 86
88 89
40 52
37 5
44 15
35 5...

output:

116425231
2353814586
35516629677
473734586751
4728475037031
47400560211380
47560119377474
47275439620868
47480397973833
47356359143869

result:

wrong answer 1st lines differ - expected: '116425574', found: '116425231'

Test #3:

score: 0

Wrong Answer

time: 2440ms

memory: 101476kb

input:

10
1000000 10 100 100000 955891 404406 316093 100 100
35 87
53 20
85 45
70 69
93 53
52 46
11 58
11 23
62 12
32 18
35 76
39 91
78 34
37 89
40 18
93 80
40 88
4 60
68 40
52 25
68 7
58 88
60 70
25 65
38 16
66 89
8 11
69 99
15 70
69 28
33 6
82 8
64 99
57 37
99 85
55 84
65 59
6 67
7 91
64 72
69 76
68 51
5...

output:

2422031406
143313745904
3432974233863
49240143056373
492552495042306
4922427443239939
4919483548271239
4921521816478305
4921670197392427
4920966060240626

result:

wrong answer 1st lines differ - expected: '2422031421', found: '2422031406'