QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#740063#9599. Dragon BloodlineI_be_wannaAC ✓229ms4580kbC++203.1kb2024-11-13 00:47:132024-11-13 00:47:14

Judging History

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

  • [2024-11-13 00:47:14]
  • 评测
  • 测评结果：AC
  • 用时：229ms
  • 内存：4580kb
查看
  • [2024-11-13 00:47:13]
  • 提交

answer

#include <bits/stdc++.h>

template < typename T >
inline void read(T &cnt) {
    cnt = 0; char ch = getchar(); bool op = 1;
    for (; ! isdigit(ch); ch = getchar())
        if (ch == '-') op = 0;
    for (; isdigit(ch); ch = getchar())
        cnt = cnt * 10 + ch - 48;
    cnt = op ? cnt : - cnt;
}

const int N = 5e4 + 5;
const int K = 20 + 5;

int n, k, a[N], b0[K], b[K];
__int128 c[N];

inline bool check(long long x) {
    for (int i = 1; i <= n; ++ i)
        c[i] = (__int128)x * a[i];
    for (int i = 1; i <= k; ++ i)
        b[i] = b0[i];

    for (int i = k; i >= 1; -- i) {
        for (int j = 1; j <= n; ++ j) {
            int level = (1 << (i - 1));
            __int128 times = c[j] / level;
            if (b[i] >= times) {
                b[i] -= times;
                c[j] -= level * times;
            }
            else {
                times = std::min(times, (__int128)b[i]);
                b[i] -= times;
                c[j] -= level * times;
            }
        }
        if (b[i] >= n) return 1;
        if (b[i]) {
            std::nth_element(c + 1, c + 1 + (n - b[i]), c + 1 + n);

            for (int q = n - b[i] + 1; q <= n; ++ q)
                c[q] = 0;
        }
    }

    for (int i = 1; i <= n; ++ i)
        if (c[i]) return 0;
    return 1;
}

inline void solve() {
    read(n), read(k);
    for (int i = 1; i <= n; ++ i)
        read(a[i]);
    for (int i = 1; i <= k; ++ i)
        read(b0[i]);
    long long l = 0, r = 2.1e15, ans = 0;
    while (r >= l) {
        long long mid = (l + r) / 2;
        if (check(mid)) {
            l = mid + 1;
            ans = std::max(ans, mid);
        }
        else r = mid - 1;
    }
    std::cout << ans << '\n';
}

int main() {
    int t; read(t);
    while (t --) solve();
    return 0;
}
/*#include <bits/stdc++.h>

template < typename T >
inline void read(T &cnt) {
    cnt = 0; char ch = getchar(); bool op = 1;
    for (; ! isdigit(ch); ch = getchar())
        if (ch == '-') op = 0;
    for (; isdigit(ch); ch = getchar())
        cnt = cnt * 10 + ch - 48;
    cnt = op ? cnt : - cnt;
}

const int N = 5e4 + 5;
const int K = 20 + 5;

int n, k, a[N], b0[K], b[K];
__int128 c[N];

inline bool check(long long x) {
    for (int i = 1; i <= n; ++ i)
        c[i] = (__int128)x * a[i];
    for (int i = 1; i <= k; ++ i)
        b[i] = b0[i];

    for (int i = k; i >= 1; -- i) {
        for (int j = 1; j <= n; ++ j) {
            int level = (1 << (i - 1));
            __int128 times = c[j] / level;
            if (b[i] >= times) {
                b[i] -= times;
                c[j] -= level * times;
            }
            else {
                times = std::min(times, (__int128)b[i]);
                b[i] -= times;
                c[j] -= level * times;
            }
        }
        if (b[i] >= n) return 1;
        if (b[i]) {
            std::nth_element(c + 1, c + 1 + (n - b[i]), c + 1 + n);

            for (int q = n - b[i] + 1; q <= n; ++ q)
                c[q] = 0;
        }
    }

}

int main() {
    int t; read(t);
    while (t --) solve();
    return 0;
}
*/
源文件, 语言: C++20

这程序好像有点Bug，我给组数据试试？

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3836kb

input:

6
4 3
1 2 3 4
4 4 4
3 2
1 1 1
1 7
3 4
6 6 2
1 1 5 5
3 5
3 1 1
1 1 1 1 1
4 5
1 9 9 8
2 2 2 3 1
5 4
1 3 1 7 1
4 1 5 2

output:

2
4
4
5
2
3

result:

ok 6 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

1
1 20
1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

output:

1048575000000000

result:

ok single line: '1048575000000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

2
3 2
1 1 1
1 7
4 2
1 1 1 1
1 2

output:

4
0

result:

ok 2 lines

Test #4:

score: 0
Accepted
time: 229ms
memory: 4580kb

input:

1
50000 20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

1048575

result:

ok single line: '1048575'

Test #5:

score: 0
Accepted
time: 126ms
memory: 3584kb

input:

1000
37 20
2 8 8 7 8 7 4 6 7 4 7 4 8 4 4 5 8 3 5 5 7 7 10 6 3 2 5 3 5 8 3 6 2 4 7 3 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
9 12
4 7 12 6 12 18 11 35 19
3 8 2 6 3 6 4 3 8 4 4 9
26 13
9 9 5 3 4 5 2 10 4 6 6 9 5 3 9 10 6 2 10 4 2 9 9 3 9 3
1 1 1 1 1 1 1 1 1 1 1 1 1
33 18
3 5 3 3 4 1 4 3 1 4 5 1 3 4 ...

output:

0
222
0
18103
0
0
0
12
0
90
0
77
4
0
78
4
5
18
0
11
0
47
0
0
2307
85
0
571
352
16
0
39
1
21
0
1
0
0
5631
795
0
231
0
0
1615
0
0
0
0
0
91
0
5
9
13
264
493
156
0
0
29
0
8191
0
138
0
1
0
0
0
100
0
0
136
98
160
0
0
3
149
0
0
1593
0
0
10532
2437
0
0
1
52
50
0
11
0
88587
395
0
0
8
0
0
76
79
0
0
0
0
0
0
17...

result:

ok 1000 lines

Test #6:

score: 0
Accepted
time: 124ms
memory: 3552kb

input:

1000
41 19
107903 130845 115094 130845 130845 130845 198182 134473 127001 197174 134662 115094 130845 134662 130845 115094 115094 134473 127001 127001 127001 130845 107903 127001 115094 130845 130845 169458 197174 107655 134473 134662 198182 130845 134473 134662 107655 127001 197174 169458 107655
1 ...

output:

0
0
310
83
0
412
13106
0
0
0
0
1
0
0
0
0
0
127
0
0
0
0
13
0
0
3510
0
0
0
0
494
0
1
13
10
0
0
2
0
533
4
0
1
0
0
1
0
0
326
4
7
0
0
1804
17
15
35
8
0
0
631
58742
5
0
0
22031
8
0
0
3
127
20
31
5984
0
1
650
0
4
0
1
10
0
3
0
1
0
0
8
20
0
1
5649
3071
0
66
0
0
0
0
0
0
0
157
3
1
1
0
1
0
0
0
0
0
1
0
0
0
0
0
1...

result:

ok 1000 lines

Test #7:

score: 0
Accepted
time: 126ms
memory: 3584kb

input:

1000
38 20
4 1 4 3 2 3 3 5 3 4 5 1 2 5 2 2 1 3 2 3 4 4 2 2 3 1 2 4 2 3 5 2 3 4 3 1 1 5
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
20 18
329 1356 2320 141 1113 41 227 1733 634 200 1084 484 1388 899 207 1266 75 31 42 220
10 10 10 10 10 10 10 10 10 2 10 10 5 1 1 2 4 4
43 12
2 4 5 4 1 5 2 2 5 1 4 2 2 2 2 4...

output:

17749
52
0
0
203
0
68
4
0
0
0
866
16
294
0
11
104
27
0
0
0
11351
6931
3
420
0
0
0
0
1
0
0
8
232
3
1187
0
0
0
0
0
10270
0
374
591
0
0
1
0
0
9
0
0
5
0
0
2
0
8
3604
0
22
543
157
18
0
21064
10
22
76
12077
172
0
0
0
70
0
0
1
0
1
33
0
0
0
0
351
0
0
138
0
0
45
8
0
1
0
108
73
64
584
0
6667
70
0
0
0
0
0
2
0
...

result:

ok 1000 lines

Test #8:

score: 0
Accepted
time: 108ms
memory: 3776kb

input:

1000
30 18
179 1089 397 121 783 421 1417 753 460 1571 528 587 588 835 1575 229 583 1592 2077 1149 171 212 135 264 784 39 137 131 372 924
512 949 442 483 63 39 774 16 202 46 620 59 13 1 48 5 1 887
32 12
3 1 1 8 8 6 8 11 5 7 7 4 22 28 12 11 45 12 19 9 20 11 11 7 12 5 10 12 15 4 3 6
242 363 937 310 974...

output:

5881
7963
747
2224
0
0
86222
0
1
584
1
55679
109
0
24362
0
2702
6817
7251
0
16
0
301618
838831
0
19826
0
297
0
0
1537
0
96
8161
0
26
729
37
21245
987854
15342
22195
1088
1709
20398
467
229902
0
0
2416
77
1428
18395
3074
0
0
84214
3778927
323657
259836
570
0
0
0
0
2175
215
302
171670
0
0
3942
5196
30...

result:

ok 1000 lines

Test #9:

score: 0
Accepted
time: 113ms
memory: 3608kb

input:

1000
38 2
4 4 13 10 5 5 6 4 9 10 1 7 5 14 4 18 6 6 19 14 8 5 1 6 11 7 1 3 4 1 15 9 14 7 6 20 2 10
95717 48431
50 17
346 373 951 6504 1115 1127 359 3238 10793 3258 2070 689 1905 729 3080 2413 1721 4049 2980 437 4997 108 1043 1081 1696 1750 1063 2546 95 4460 33 618 626 1579 5890 1284 487 665 36 255 34...

output:

655
76375
78152993
11910291
0
8128
0
6976967
143369993
0
26539
31197665
65147
106730142
2425163
33075
8646
0
0
0
13583
775726
901878
0
0
231627883
0
3286
32537
29332561
770
689987
1
95902
301300
25621178
2537304
37903
15397
0
0
53
1598535
101829
1993
0
22334352
13253
1408073
221080
1640
8622
118707
...

result:

ok 1000 lines

Test #10:

score: 0
Accepted
time: 114ms
memory: 3552kb

input:

1000
36 11
1 3 1 1 5 3 1 1 1 5 3 1 1 5 5 3 2 3 2 3 2 2 2 2 2 2 5 2 4 3 5 2 3 1 5 5
9567 9567 9567 9567 9567 9567 9567 9567 9567 9567 9567
47 18
2 11 7 8 5 2 8 8 10 4 13 13 6 5 13 1 2 8 7 5 7 4 18 2 9 7 10 5 2 5 2 4 3 1 6 10 1 7 2 7 1 1 8 13 16 14 6
7415468 5423045 7975741 6627997 5278107 5756200 349...

output:

201893
4587886145
4288
0
62375442
0
0
30865696
882603021
226868
93
236981
301843
0
620942
0
650785
0
1315107322
10932
0
59060102
0
0
1766356869
13908678436
42504
86167100
982016
0
61037402
0
664561
425612169
130276
0
31545692
403549945
447292164
20682
21438
0
672853650
0
55015880
44364
0
2580781
138...

result:

ok 1000 lines

Test #11:

score: 0
Accepted
time: 114ms
memory: 3852kb

input:

1000
42 12
10 3 16 12 15 11 9 3 10 5 2 12 6 1 14 3 11 9 5 7 14 18 7 9 6 9 5 11 8 12 14 7 25 19 5 9 26 6 16 6 5 4
434380089 600711172 745844756 686292204 314118332 490673709 327985514 402540912 886748861 700432070 412305373 896525442
37 20
290204814 410688375 410688375 284838705 284838705 447231279 4...

output:

7277202509
0
70716
9983247432056
0
15190559852
7816583872
204052
4660303
0
3513494
81156126929
1612983
123167373356
0
339534188509
7112008
135393
2063547
2916008579679
114978878759
2241054026967
0
0
1907092
0
0
461145
3391087
1113688
679845
962808
2309148092948
0
1996439
2571284760
0
0
88969331743
5...

result:

ok 1000 lines

Test #12:

score: 0
Accepted
time: 114ms
memory: 3572kb

input:

100
355 19
4 2 2 2 5 2 1 1 5 2 1 5 3 3 2 4 5 1 4 4 3 1 2 5 2 3 5 2 3 5 1 1 1 2 3 4 5 1 5 4 5 3 1 2 5 4 5 2 2 2 1 5 1 2 4 4 2 1 4 1 4 4 4 2 5 1 3 3 1 2 5 1 3 4 4 3 3 5 3 4 3 1 2 3 3 2 1 3 4 5 4 1 4 5 4 1 3 1 5 4 1 3 1 5 3 5 2 5 4 1 1 1 4 5 4 3 1 1 5 3 2 4 4 3 5 4 4 2 2 4 2 4 5 2 1 2 1 3 2 4 1 5 3 5 2...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
46437
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
69
0
0
0
0
0
0
0
0
0
0
0
315
0
0
0
0
0

result:

ok 100 lines

Test #13:

score: 0
Accepted
time: 108ms
memory: 3820kb

input:

100
454 18
427019 147589 84095 265542 271011 468024 590508 135943 84298 346254 168638 327833 495794 530540 217096 114832 215043 82884 540679 295281 231490 260647 305295 149608 441693 575238 298713 20642 190563 395677 131111 142577 432190 67330 1330923 299096 71860 221479 6380 154275 517135 447162 20...

output:

0
150199
0
0
2530
1807
236831
0
0
15595
573
0
0
0
378
0
0
1868
0
0
226
1865
1726
0
0
31054
4344
50104
313
0
0
182949
0
6501
0
539
38358
9176
0
1409
33
0
633
4195
3670
84711
0
144
0
3325
0
14
173
15810
1
13124
148
3546
706
20
667
0
2137
0
380
0
0
4253
0
535
10523
48082
8165
0
14
1543
73161
14860
680
...

result:

ok 100 lines

Test #14:

score: 0
Accepted
time: 99ms
memory: 3588kb

input:

100
272 4
97 146 84 228 454 653 148 122 152 419 49 179 664 486 114 304 588 311 177 377 88 273 83 292 620 352 387 233 161 232 346 209 233 202 225 496 538 333 108 1053 246 250 409 364 484 578 149 655 142 388 168 256 182 75 158 143 51 155 169 200 217 290 322 410 211 155 179 560 397 254 310 285 113 97 2...

output:

13
234949
1720083
0
0
0
69629
48459
417000
0
0
142
0
0
35284
0
87200
21058
69633
0
17021
2283742
262
3893
2486
71485
14062264
5232
461
0
734
17028
3111281
72866
0
695
624
827
159531
8482
0
12795018
0
26455
3580
183
123104
0
4105723
30855246
1011740
65335
6412546
0
0
1423554
1614128
95697
0
0
0
730
0...

result:

ok 100 lines

Test #15:

score: 0
Accepted
time: 94ms
memory: 3624kb

input:

100
412 11
495 186 304 421 369 520 368 38 406 827 1104 194 5 87 452 663 306 609 89 61 134 178 85 139 328 869 256 301 1195 280 40 769 205 593 251 43 471 220 1887 554 506 803 390 916 568 58 63 1589 99 85 1308 31 49 150 303 52 385 491 261 449 459 168 23 1030 48 123 637 351 138 657 345 501 267 139 1080 ...

output:

78430
546
0
6279
0
10125553
1935
5154
3526513054
0
191440525
563380272
77560126
0
44343496
216682
0
18880524
255066
1860490725
84954081
68042
118412
348426541
0
1121039585
734142
32813
0
67229
78719886
13080834
1252
3198
33528927
0
86647
3509
0
2948414
110200306
61254
8689
949
3815585
1860031
59584
...

result:

ok 100 lines
English 繁體中文 简体中文

服务器时间: 2024-12-03 07:27:50 | 开源项目