QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#449665#8598. AND МасивQwerty1232#10 1013ms13164kbC++231.3kb2024-06-21 15:48:502024-06-21 15:48:51

Judging History

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

  • [2024-06-21 15:48:51]
  • 评测
  • 测评结果:10
  • 用时:1013ms
  • 内存:13164kb
  • [2024-06-21 15:48:50]
  • 提交

answer

#include <iostream>
// #pragma GCC optimize("O3")
// #pragma GCC target("avx2")
#include <bits/stdc++.h>

// #define int int64_t
constexpr int B = 20;

int dp[2][1 << B + 1];

int32_t main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, b;
    std::cin >> n >> b;
    std::vector<int> input(n);
    for (int i = 0; i < n; i++) {
        std::cin >> input[i];
    }

    auto f = [&](int s, int x) -> int {
        int res = 0;
        // int x = 1 << p;
        for (int i = s; i < n; i++) {
            if (!(x & input[i])) {
                x |= input[i];
                res += i + 1;
            }
        }
        return res;
    };

    std::vector<int> ans(n);
    for (int i = n - 1; i >= 0; i--) {
        auto& dp1 = dp[i % 2];
        auto& dp2 = dp[i % 2 ^ 1];
        int val = input[i];
        for (int j = 0; j < (1 << b); j++) {
            dp2[j] = (j & val) ? dp1[j] : dp1[j + val] + (i + 1);
            // assert(dp2[j] <= 1e9);
            // assert(dp2[j] == f(i, j));
        }

        for (int j = 0; j < b; j++) {
            ans[i] += dp2[1 << j];
        }
    }
    for (int i = 0; i < n; i++) {
        std::cout << ans[i] << " \n"[i == n - 1];
    }

    return 0;
}

详细

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 744ms
memory: 13124kb

input:

2000 20
251931 620255 725521 330111 783060 690627 489092 1019106 84341 631993 231500 920886 604265 342966 152434 588032 469990 805072 809795 12697 699326 433747 754394 567737 603087 199524 539078 775214 872735 454953 106496 93877 933762 36223 211878 168057 53977 782675 171782 455544 869778 47128 955...

output:

10212 4259 4815 9101 17193 17617 22629 16642 10432 10731 11766 20234 27120 17990 24654 22106 18877 14050 9217 10109 4283 9341 11741 13465 13724 9572 11200 4046 7660 7001 6512 12634 13360 10494 19745 15300 12727 17726 14188 10472 12754 7995 10571 11290 14862 19370 16785 13328 13589 17425 23190 17082 ...

result:

ok single line: '10212 4259 4815 9101 17193 176...6 39925 39961 39974 43987 18000'

Test #2:

score: 0
Accepted
time: 1013ms
memory: 13164kb

input:

2000 20
2080 32772 278528 256 2560 1056 528384 2056 132 144 768 98304 36864 262152 262400 81920 264192 16448 294912 786432 8194 16388 9 520 49152 2 262272 20 131584 528384 514 4352 12288 36 32800 72 16392 32 129 8 1028 131080 12288 8193 8320 528 1026 24576 8192 10240 163840 524288 262400 278528 2785...

output:

10532 10275 11389 7400 12269 14740 10975 9199 12307 10890 12090 11861 12707 12449 12586 12195 12260 14273 18795 18089 19280 21369 14169 17819 13755 16253 14945 14538 24799 24439 23275 17968 19797 19977 21225 18864 16595 21665 22140 32768 31494 29782 27849 20911 26304 21480 25191 22840 30738 26969 22...

result:

ok single line: '10532 10275 11389 7400 12269 1...111837 109909 73963 71982 36000'

Test #3:

score: 0
Accepted
time: 835ms
memory: 11940kb

input:

2000 20
81937 164096 131652 98564 263184 69665 2596 557184 286848 22544 49416 196872 65816 2179 45056 135232 352 1120 8832 32801 131776 98328 528385 51456 266400 396288 65573 328200 528512 26 65700 2248 8328 322 557312 16516 34050 66624 721152 45060 524353 2448 65984 16899 20993 137 265248 33808 665...

output:

10265 12832 12649 13394 14831 13921 19818 8209 7716 12652 12292 11823 12491 12133 17047 7964 8283 15911 12563 12580 12125 10806 12966 12370 19648 11631 12192 16886 17717 20174 20336 25578 15349 16556 21621 20009 14907 18092 15498 24250 21725 21223 14614 15274 10702 16692 16601 15963 14431 23066 1801...

result:

ok single line: '10265 12832 12649 13394 14831 ...8 75882 73929 95952 63984 32000'

Subtask #2:

score: 0
Time Limit Exceeded

Test #4:

score: 0
Time Limit Exceeded

input:

100000 20
262144 16 65536 8 256 1024 32 262144 16 262144 256 1024 1 64 2 131072 4096 2048 2 32 8192 4 2 262144 32768 1 524288 262144 262144 2048 8 64 1 2 8192 131072 256 64 8192 1 262144 4 32 4 524288 1 32768 16 64 128 8192 16 32 4096 16384 16384 4 131072 32768 16384 131072 2 16 2048 32768 16 4 4096...

output:


result:


Subtask #3:

score: 0
Wrong Answer

Test #6:

score: 15
Accepted
time: 23ms
memory: 3880kb

input:

100000 8
98 78 5 190 79 234 162 79 118 176 115 130 10 9 233 56 97 15 148 13 46 87 92 65 150 62 50 46 159 101 48 86 203 71 29 124 23 228 55 161 240 80 139 74 251 143 167 207 183 52 50 252 17 185 40 145 167 164 227 166 172 60 182 62 173 227 232 243 251 134 109 241 44 33 217 149 51 6 110 201 242 196 23...

output:

152631657 152630131 152630001 152630939 152631411 152631998 152630663 152631609 152631606 152630657 152631172 152632208 152631468 152631040 152631058 152630747 152631208 152630998 152631307 152631149 152631038 152631013 152631782 152631146 152631829 152632118 152632297 152632294 152631891 152632567 ...

result:

ok single line: '152631657 152630131 152630001 ...4 1199980 1199981 699995 500000'

Test #7:

score: 0
Accepted
time: 23ms
memory: 3940kb

input:

100000 8
132 32 160 18 136 6 72 24 129 32 5 96 128 33 144 12 3 68 24 132 144 128 80 12 40 36 130 132 3 5 144 136 33 65 3 18 24 68 2 4 17 5 129 17 80 24 80 66 96 3 80 132 40 24 33 4 16 32 16 160 136 65 68 36 17 33 48 130 129 132 72 144 136 80 32 4 72 130 12 2 68 80 3 16 144 72 18 66 160 72 5 12 96 33...

output:

5952637 5952720 5953709 5952776 5952715 5952598 5952795 5953843 5953869 5954350 5953227 5952731 5953557 5953953 5953969 5953654 5952917 5952989 5954434 5954010 5954470 5953077 5954247 5953906 5953896 5954919 5954403 5954223 5953545 5953497 5953678 5953920 5954491 5954953 5954882 5954021 5954016 5954...

result:

ok single line: '5952637 5952720 5953709 595277...1 1299969 799987 1199994 600000'

Test #8:

score: 0
Accepted
time: 23ms
memory: 3908kb

input:

100000 8
141 194 198 43 134 49 74 204 148 34 240 131 116 50 147 146 20 76 161 60 99 38 3 38 98 24 164 98 240 149 99 163 27 82 108 184 37 26 102 152 25 3 77 78 73 141 53 137 78 130 226 81 212 226 162 149 41 177 112 29 7 197 216 13 74 154 161 28 50 99 113 216 14 57 134 131 135 51 6 69 141 73 116 194 7...

output:

4055305 4050887 4052706 4047838 4067390 4067423 4056658 4059069 4044709 4044152 4050128 4050231 4087336 4087869 4062113 4069179 4054377 4053586 4047213 4080771 4060526 4077103 4045902 4077653 4042666 4050004 4061909 4050714 4046983 4048224 4041638 4049613 4093973 4080069 4071289 4050701 4067381 4049...

result:

ok single line: '4055305 4050887 4052706 404783...974 799983 799989 699995 400000'

Test #9:

score: 0
Accepted
time: 21ms
memory: 3812kb

input:

100000 8
124 54 93 174 195 135 125 181 30 79 220 243 226 188 57 193 148 73 234 185 187 119 205 143 234 191 151 222 135 198 153 113 180 75 79 62 204 175 150 204 248 59 165 232 124 207 171 15 105 211 241 47 235 181 99 46 109 38 187 222 27 218 149 158 106 196 143 146 59 118 151 185 246 22 215 51 209 11...

output:

8334577 8411953 8475901 8619180 8653164 8489145 8500880 8394518 8477544 8448102 8432858 8562386 8402286 8379389 8400932 8370201 8397679 8371556 8408604 8457393 8490636 8418500 8324620 8331736 8301641 8278722 8296598 8312416 8381676 8311669 8389405 8526662 8512198 8463133 8270940 8316768 8345109 8249...

result:

ok single line: '8334577 8411953 8475901 861918...977 799983 699990 699996 500000'

Test #10:

score: 0
Accepted
time: 21ms
memory: 3816kb

input:

100000 8
9 2 3 8 5 69 5 3 67 9 11 5 6 10 5 6 5 4 5 21 6 10 6 10 9 137 2 8 3 67 1 5 9 5 8 9 6 2 6 5 10 12 6 8 9 6 10 3 10 6 9 5 6 3 1 9 4 2 3 9 1 9 4 9 10 6 1 9 3 6 10 6 8 2 9 6 5 9 5 1 5 8 4 9 6 4 5 6 9 8 12 8 4 2 8 5 4 9 10 4 2 6 5 2 5 1 4 132 3 9 6 70 5 9 8 5 3 11 10 9 3 6 9 10 18 10 3 5 4 8 3 8 9...

output:

210888808 210888792 210888825 210888885 210888889 210695006 210888901 210889018 210695102 210888908 210888918 210888940 210888996 210888949 210889001 210889024 210889009 210889167 210889030 210884920 210889091 210889379 210889105 210889452 210889468 210609577 210889672 210889451 210889500 210695597 ...

result:

ok single line: '210888808 210888792 210888825 ...976 599983 599988 599995 400000'

Test #11:

score: 0
Accepted
time: 17ms
memory: 3888kb

input:

100000 8
6 132 129 5 4 5 128 1 129 5 2 128 5 2 129 5 132 1 129 1 5 13 6 132 5 6 129 5 2 4 132 5 6 1 4 2 6 132 5 132 128 129 132 5 132 6 10 128 129 128 132 128 4 6 130 6 132 129 4 5 4 5 6 129 6 8 6 1 4 132 129 137 6 1 5 129 161 128 129 145 5 4 6 5 1 128 5 6 5 1 5 6 132 2 6 130 128 130 129 5 2 128 2 1...

output:

102876418 102876497 102876497 102876524 102876578 102876561 102876753 102876788 102876694 102876630 102876648 102876669 102876774 102876732 102876693 102876941 102876827 102876924 102876733 102876938 102876957 102876591 102876796 102876930 102876984 102876813 102876975 102877083 102877299 102877348 ...

result:

ok single line: '102876418 102876497 102876497 ...975 699982 699987 699994 600000'

Test #12:

score: -15
Wrong Answer
time: 21ms
memory: 3860kb

input:

100000 8
128 130 64 68 64 128 136 64 128 192 128 64 192 128 160 128 160 128 160 128 64 0 0 0 0 64 128 64 128 160 0 128 64 128 160 128 136 128 64 72 128 64 192 128 64 66 64 128 64 96 64 192 64 128 132 128 136 128 64 128 192 128 130 0 64 128 192 64 96 0 0 128 160 128 64 128 64 66 64 65 0 144 64 128 13...

output:

234504492 234130127 234504527 234204907 234504541 234504562 234279595 234504583 234504611 234504547 234504625 234504646 234504577 234504709 234502929 234504723 234502943 234504737 234502957 234504751 234504800 234504835 234504659 234504475 234504283 234504083 234504097 234504111 234504146 234502367 ...

result:

wrong answer 1st lines differ - expected: '4529471788 4529097423 45294718... 1499980 1499986 1399994 800000', found: '234504492 234130127 234504527 ... 1499980 1499986 1399994 800000'

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%